Educational Codeforces Round 121 (Rated for Div. 2) 补E

题意

给定一棵 n n n个节点的树，至少有两个黑色的节点。现在你在某个节点上，操作为：你可以选择任意一个黑色节点向它走一步。对于任意两个相邻的操作不能选择同一个黑色的节点。

对于树上的每个节点，判断能否从该节点出发，通过有限次操作到达某一黑色节点。

思路

我们先考虑能够到达的情况：

1. 对于某个黑色点的本身以及相邻点都是一定能够到达的：

   

   将这种情况具体化，发现当白色节点所在的白色联通块和所有黑色节点相邻时，该白色节点无法到达黑色节点。

2. 对于子树某条链上存在两个黑色节点的情况，则可以通过切换目标点的方式到达第一个黑点：

   

   将这种情况具体化，可以发现，如果一个点与黑点相邻的同时，某一方向的子树中存在黑点，那么其它所有方向的子树都可以到达黑色节点。在这种特例下，第一种情况也可以到达。

那么只需要两次DFS即可

Accepted Code

#include 
#define endl '\n'
using namespace std;

const int N = 3e5 + 10;
int n = 0, a[N], ans[N], cnt[N], summ = 0;
vector g[N];

//向子树方向搜索统计满足2条件的子树方向的黑色节点数(以该点为根节点，临接黑点且子树黑点大于两个)
void dfs1(int u, int fa){
    for(int i = 0; i = 2 && ans[g[u][i]]) ans[u] = 1; 
    }
}

//向子树方向搜索，判断满足条件的向根方向的点
void dfs2(int u, int fa){
    for(int i = 0; i = 2 && ans[u]) ans[g[u][i]] = 1; 
        dfs2(g[u][i], u);
    }
}


inline void solve(){
    cin >> n;
    //for(int i = 1; i  a[i];
    for(int i = 1, u, v; i > u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }   
    for(int i = 1; i