题解：P11529 [THUPC 2025 初赛] 辞甲猾扎

Tmbcan · 2025-09-29 14:48:31 · 题解

想了两年半砸贪心。

思路

设与黑点相邻，且不为黑点的点集为 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;
}