Codeforces Round #746 (Div. 2) C - Bakry and Partitioning
题意：
给出一个带点权的树和k，删除[ 1 , k − 1 ]条边，问能否存在某种方案使得删边后的所有子树的异或值相等。
思路：
参考视频
一个关于异或的技巧就是：如果当前答案可以是5个的话，也可以是3个；如果当前答案是4个的话，可以是2个。一般都是取小的值。
那么这个题也是类似的技巧，最后尽量是变成3棵子树或2棵子树，也就是说要删除2条边或1条边。
假设这棵子树的总异或值为s u m，当s u m = = 0时，一定可以拆成两棵子树。比如一棵子树的权值为x，那么剩下的子树权值也为x，这样总异或和才为0.
如果s u m ! = 0的话，就要看能否分成三棵子树，每一棵子树的和都为s u，这样最后的总的异或和也为s u m。
具体方法是做一遍d f s，每次如果发现某棵子树的异或和为s u m，就计数器n o w + +，并且清空这棵子树的异或和。
最后判断如果n o w > = 3 & & k > = 3的话，就可以分成。
k > = 3是保证可以删边，n o w > = 3是保证可以拆成3棵子树，如果n o w > 3的话，可以把多个合为一个，这样异或值还是一样的。
在这一步里，n o w一定是个奇数，所以每次只需要把多出来的偶数个放到一个上就可以了。
代码：
// Problem: C. Bakry and Partitioning // Contest: Codeforces - Codeforces Round #746 (Div. 2) // URL: https://codeforces.com/contest/1592/problem/C // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; vector<ll>g[maxn]; ll n,k,a[maxn],sum,now,flag,b[maxn]; void dfs(int u,int fa){ b[u]=a[u]; for(auto it:g[u]){ if(it==fa) continue; dfs(it,u); b[u]^=b[it]; } if(b[u]==sum){ now++; b[u]=0; } } int main(){ int _=read; while(_--){ n=read,k=read; sum=0;flag=0;now=0; rep(i,1,n) g[i].clear(); rep(i,1,n) a[i]=read,sum^=a[i]; for(int i=1;i<n;i++){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } if(sum==0) flag=1; else dfs(1,0); if(now>=3&&k>=3) flag=1; //cout<<now<<endl; if(flag) puts("YES"); else puts("NO"); } return 0; }
