Codeforces Round #746 (Div. 2) C.D

C.Bakry and Partitioning

Problem Analysis

题目描述：对于给定的一棵树，判断能否通过删除 1 1 1~ k − 1 k-1 k−1条边，使删边后的森林中的每个连通块的异或和相等。

思路：思路比较巧妙：对于异或操作，我们容易知道对于任意整数 n n n：

1. n   x o r   n = 0 n\ xor\ n = 0 n xor n=0 ；
2. 0   x o r   n = n 0\ xor\ n = n 0 xor n=n；
3. 1 , 2 → n   x o r   n   x o r   n = n 1,2 \rightarrow n\ xor\ n\ xor\ n= n 1,2→n xor n xor n=n。

那么对于整棵树而言，如果异或和为 0 0 0，那么必然可以通过删去一条边得到两个异或值相等的连通块，此时直接输出yes。

如果异或值不为 0 0 0，设为 n n n，那么至少有 3 3 3个以上的连通块异或值为 n n n，才有机会得到预期答案。但要注意，如果 k ≤ 2 k\leq2 k≤2，那么无法分割连通块。

Accepted Code

#include 
#define pb push_back
#define int long long
using namespace std;

inline int read(){
    int f = 1, x = 0; char s = getchar(); 
    while(s  '9'){ if(s =='-') f = -1; s = getchar(); } 
    while(s >= '0' && s  v;
        g[u].pb(v);
        g[v].pb(u);
    }
    if(!xorsum){
        cout