题解：CF1626E Black and White Tree

· · 题解

题目传送门

首先，对于任意点 x 为根，有 3 种情况能走到黑点：

如果以每个点为根暴力 dfs 肯定会超时，所以我们先以 1 为根搜出每棵子树 y 中的黑点个数 si_y，并求出每个节点是否能从自己儿子 son 走到黑点，如样例，(8,5,7,2) 均可行。 再进行第二次搜索，把自己父亲 f_x 看作一个儿子，父亲的黑点数为总黑点数 cnt 减当前节点的黑点数 si_x，再进行判断即可。

代码附上————

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int maxn = 300010;
const int inf = 1e9;
//unsigned long long 
//cout << fixed << setprecision(3)
//cout << setw(5) << 
//continue
int a[maxn], si[maxn], f[maxn], cnt, cnt1, t[maxn * 2], nxt[maxn * 2], head[maxn];
bool ans[maxn];
void add(int x, int y){
    cnt1++;
    t[cnt1] = y;
    nxt[cnt1] = head[x];
    head[x] = cnt1;
}
void dfs(int x, int fa){
    si[x] = a[x];
    f[x] = fa;
    for(int i = head[x];i;i = nxt[i]){
        int to = t[i];
        if(to == fa) continue;
        dfs(to, x);
        si[x] += si[to];
        if(a[to] || (si[to] >= 2 && ans[to])){
            ans[x] = 1;
        }
    }
}
void dfs1(int x, int fa){
    if(a[fa]) ans[x] = 1;
    for(int i = head[x];i;i = nxt[i]){
        int to = t[i];
        if(to == fa) continue;
        if(ans[x] && si[1] - si[to] >= 2){
            ans[to] = 1;
        }
        dfs1(to, x);
    }
}
signed main(){
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        cnt += a[i];
        ans[i] = a[i];
    } 
    // cout << cnt << endl;
    for(int i = 1;i < n;i++){
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    dfs(1, 0);
    dfs1(1, 0);
    for(int i = 1;i <= n;i++){
        cout << ans[i] << ' ';
    }
    return 0;
}

感谢阅读！