题解：P10723 [GESP202406 七级] 黑白翻转

· · 题解

第一眼感觉很难，上手推下发现还好？

题意：

给定一棵树，只有黑色和白色节点，求反转最少的白色节点变为黑色节点，使得所有的黑色节点能构成一棵树。

思路：

考虑一种情况 首先，黑点肯定是不能动的。\ 想让整个树删完白色点后还为一棵树，且反转操作尽可能少，显然要将这幅图中的 3 号点反转。\ 此时次数最少且变为美丽树。

于是可以得出一条结论：当当前节点的子节点中含有黑色节点时，显然当前节点需要反转，答案加一。

如果不反转则必然构不成一棵树。 (会被白点分开)\ 则此做法可得最少操作次数。\ ( 不会证 )\ 在遍历树的时候顺便算一下就行了。\ (注意：因为此题是无根树，所以当根节点为白色时，没法将根节点考虑在内，结果并不是最优，所以根节点要为黑色，具体原因其他题解有作出解释。)\ (好题，使我的咕值旋转。)

AC code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int n,a[N],flag=0,root,tot=0,nbs[N],ans=0;
struct edge{
    int ed,next;
}b[N*2];   //链式前向星建图
void add(int x,int y){
    tot++;
    b[tot].next=nbs[x];
    b[tot].ed=y;
    nbs[x]=tot;
}
void dfs(int k,int fa){
    for(int x=nbs[k];x;x=b[x].next){
        int u=b[x].ed;
        if(u==fa)continue;
        dfs(u,k);    //遍历到叶子节点
        if(a[k]==0 && a[u]==1){   //统计
            ans++;
            a[k]=1;  //翻转
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1 && !flag){    //找根
            flag=1;
            root=i;
        }
    }
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(root,-1);
    cout<<ans;
    return 0;
}

第一次写题解，望审核大大给过 QWQ，有错误请指出，感谢。