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

Redamancy_Lydic · 2024-07-09 20:31:50 · 题解

背景

汗流浃背了。

分析

容易想到一个显然的思路：以任意节点为根，开始遍历。如果一个节点的子树里面有黑点，那么它必须保留，否则如果它是白点，则可以删去。

但这个方法很容易举出反例：

在这颗树中，如果以最上面的白点为根，那么手推发现算法显然错误。

尝试进行修改，容易发现，对于类似的情况，我们只需要以一个黑点为根，就可以轻松解决。

还有一类特殊情况，如果原树里面全是白点，那么输出 0 即可。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int w=1,s=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
    return w*s;
}
const int mod=1e9+7;
const int maxn=1e6+10;
int n,d[maxn];
vector<int> G[maxn];
bool siz[maxn];
void dfs(int x,int fa)
{
    if(d[x])siz[x]=1;
    for(auto y : G[x])
    {
        if(y==fa)continue;
        dfs(y,x);
        siz[x]|=siz[y];
    }
}
int du[maxn];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)d[i]=read();
    bool ff=0;
    for(int i=1;i<=n;i++)ff|=d[i];
    if(!ff)return 0*printf("%lld\n",0);
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        G[x].push_back(y);
        G[y].push_back(x);
        du[x]++;du[y]++;
    }
    int root=1;
    for(int i=1;i<=n;i++)if(d[i]==1)root=i;
    dfs(root,0);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0&&siz[i])ans++;
    }
    cout<<ans;
    return 0;
}