Codeforces Round #746 (Div. 2) C - Bakry and Partitioning
题意：
给出一个带点权的树和 k k k，删除 [ 1 , k − 1 ] [1,k-1] [1,k−1]条边，问能否存在某种方案使得删边后的所有子树的异或值相等。
思路：
一个关于异或的技巧就是：如果当前答案可以是 5 5 5个的话，也可以是 3 3 3个；如果当前答案是 4 4 4个的话，可以是 2 2 2个。一般都是取小的值。
那么这个题也是类似的技巧，最后尽量是变成
3
3
3棵子树或
2
2
2棵子树，也就是说要删除
2
2
2条边或
1
1
1条边。
假设这棵子树的总异或值为
s
u
m
sum
sum，当
s
u
m
=
=
0
sum==0
sum==0时，一定可以拆成两棵子树。比如一棵子树的权值为
x
x
x，那么剩下的子树权值也为
x
x
x，这样总异或和才为
0
0
0.
如果
s
u
m
!
=
0
sum!=0
sum!=0的话，就要看能否分成三棵子树，每一棵子树的和都为
s
u
m
sum
sum，这样最后的总的异或和也为
s
u
m
sum
sum。
具体方法是做一遍
d
f
s
dfs
dfs，每次如果发现某棵子树的异或和为
s
u
m
sum
sum，就计数器
n
o
w
+
+
now++
now++，并且清空这棵子树的异或和。
最后判断如果
n
o
w
>
=
3
&
&
k
>
=
3
now>=3\&\&k>=3
now>=3&&k>=3的话，就可以分成。
k
>
=
3
k>=3
k>=3是保证可以删边，
n
o
w
>
=
3
now>=3
now>=3是保证可以拆成
3
3
3棵子树，如果
n
o
w
>
3
now>3
now>3的话，可以把多个合为一个，这样异或值还是一样的。
在这一步里，
n
o
w
now
now一定是个奇数，所以每次只需要把多出来的偶数个放到一个上就可以了。
代码：
// 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;
}