题解：黑白翻转 [GESP202406]

@Author ylch 2025-12-14
疑似重题“[ABC368D] Minimum Steiner Tree”

思路1：任意两个黑点之间的所有白点都不能被删除，所以只需要把两个黑点之间的所有白点都变成黑点就可以。
为什么这样是正确的？因为这是一颗树，若两个黑点之间有一个白点，那么删掉它肯定是不行的，否则图会不连通。
所以我们只要以一个黑点为根，向下，若能到另外一个黑点，这期间的所有白点都会变成黑点。

思路2：发现最后留下的联通子图是唯一的，树上求子图，考虑树上dp
设dp[i]表示以i为根的子树中白点的数量
转移显然：$dp[u]=(c[v]==0)+\sum\limits_{v \in son(u)} dp[v]$
答案显然即为dp数组中非0元素的个数
还有一个问题，所有白色结点的lca到根这一块dp数组是非0的，但这些结点并不包含在答案中
求lca再特判太麻烦，考虑做dp时以任意一个白点为根即可

思路3：考虑类似拓扑排序
最后合法的图一定是白色结点都位于最外部（类似于叶子）的位置，然后整个树的主干部分都是黑色
那么我们考虑用拓扑，每次把入度为0的白色结点删去并更新，直到无法删除，那么剩下的白点就都是要删的了

// 思路3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;

int n, a[maxn], d[maxn], ans;
vector<int> T[maxn];

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i]; ans += !a[i]; // ans统计白点个数
    }
    for(int i = 1; i <= n - 1; i ++){
        int u, v; cin >> u >> v;
        T[u].push_back(v); T[v].push_back(u);
        d[u] ++, d[v] ++;
    }
    queue<int> Q;
    for(int i = 1; i <= n; i ++){
        if(d[i] <= 1 && !a[i]) Q.push(i), a[i] = 1, --ans; // 把度数为0的也算进来
    }
    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        for(int v : T[u]){
            if(--d[v] <= 1 && !a[v]) Q.push(v), a[v] = 1, --ans;
        }
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}