P11529 [THUPC 2025 初赛] 辞甲猾扎

想了两年半砸贪心。

思路

设与黑点相邻，且不为黑点的点集为 \(S\)。

不难发现答案上界是 \(|S|\)。
如果对于两个点 \(i,j \in S\)，存在 \((u,i)\) 和 \((u,j)\)，那么我们有可能通过选择 \(u\) 作为白点来优化答案。

实际我们要做的工作是使得 \(\forall i \in S\)，\(i\) 为白点或者与一个白点相邻。

于是，我们在树上先删去所有黑点，再删去所有不属于 \(S\) 且与 \(S\) 中的点不相邻的点。
操作完后整个图变成了森林，我们要在这个森林上对 \(S\) 做类似最小支配集的东西。

考虑我们怎么对一个树做最小支配集。从叶子向上贪心，如果一个点 \(u\) 没有被支配且没在支配集中，那么将 \(fa_u\) 放入支配集中，这样可以使得 \(fa_{fa_u}\) 也被支配那么答案一定不劣。

我们在森林上做上面的过程就可以了，只不过条件变为只要 \(S\) 被支配即可。

代码

const int N = 1e6+10;
int n,m,ans;
struct{int to,nex;
}edge[N];
int head[N],edge_num;
inline void add(int x,int y){edge[++edge_num].to = y;edge[edge_num].nex = head[x];head[x] = edge_num;
}
struct Edge{int u,v;
}ed[N];
int B[N],W[N];
int is_dfs[N],vis[N],in_st[N],fa[N];
inline void dfs(int now,int fu){is_dfs[now] = 1;fa[now] = fu;for(int i=head[now];i;i=edge[i].nex){int tto = edge[i].to;if(tto==fu) continue;dfs(tto,now);}if(!vis[now] && W[now]){if(!in_st[fa[now]]){in_st[fa[now]] = 1;++ans;}vis[now] = 1;vis[fa[now]] = 1;vis[fa[fa[now]]] = 1;}
}
int main(){// freopen("in.in","r",stdin);// freopen("out.out","w",stdout);read(n,m);for(int i=1,x;i<=m;++i){read(x);B[x] = 1;}for(int i=1,u,v;i<n;++i){read(u,v);if(B[u] && !B[v]) W[v] = 1;if(B[v] && !B[u]) W[u] = 1;if(B[u] || B[v]) continue;ed[i] = {u,v};}for(int i=1;i<n;++i){if(W[ed[i].u] || W[ed[i].v]){add(ed[i].u,ed[i].v);add(ed[i].v,ed[i].u);}}for(int i=1;i<=n;++i){if(!is_dfs[i] && W[i]){dfs(i,i);}}printf("%d",ans);fclose(stdin);fclose(stdout);return 0;
}