Codeforces Round #746 (Div. 2)——C. Bakry and Partitioning（树形结构）

给出包含n个节点n-1条边的一棵树，每个节点有对应的点权，
给出k（2<= k <=1e5），要求删除至少一条边，至多k-1条边，
若存在某种方案，使删边后的森林中，每棵树的所有节点总异或值都相等，输出yes，反之no。

假设原树Tree的总异或值为x，分析k可知，最终方案要么只删一条边要么删两条边，以下是几种可行情况：
1、若x==0，随意断开一棵子树。
（子树总异或值为y，x ⨁ bigoplus ⨁ y == 0 ⨁ bigoplus ⨁ y == y)
2、若x!=0，存在一棵子树Tree1的总异或值为0，且Tree1存在一个子节点（一棵子树）Tree2的总异或值为x，断开这两棵树。
（最终的森林包含三棵树：Tree-Tree1，Tree1-Tree2，Tree2，各自的总异或值为：x ⨁ bigoplus ⨁ 0 == x，0 ⨁ bigoplus ⨁ x == x，x）
3、若x!=0，存在一棵子树Tree1的总异或值为x，且除Tree1所有子节点和父节点外，还存在一棵子树Tree2总异或值也为x，断开它们。
（最终的森林包含三棵树：Tree-Tree1-Tree2，Tree1，Tree2，各自的总异或值为：x ⨁ bigoplus ⨁ x ⨁ bigoplus ⨁ x == x， x， x）

#include
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int n, k;
int val[100005], siz[100005], tot, ans;
vector eg[100005];
map sum, vis;

void dfs1(int x, int far)
{
	for(auto y:eg[x])
	{
		if(y == far) continue;
		dfs1(y, x);
		val[x] ^= val[y];
		siz[x] += siz[y];
	}
	siz[x] += (val[x]==tot); // 子树（含本身）中异或值为tot的数量
	sum[val[x]] ++; // 记录整棵树中异或值为tot的子树个数
}
void dfs2(int x, int far)
{
	if(val[x] == tot && vis[0]) ans = 1; // 存在异或值为0的父节点(vis[0])，且当前子树异或值为tot
	if(val[x] == tot && siz[x] + vis[tot] < sum[tot]) ans = 1;
	//当前子树异或值为tot且除去子节点(siz)，父节点(vis)外，还存在一棵树异或值为tot
	
	vis[val[x]] ++;
	for(auto y:eg[x])
	{
		if(y == far) continue;
		dfs2(y, x);
	}
	vis[val[x]] --;
}
void solve()
{
	cin>> n >> k;
	tot = 0;
	for(int i=1;i<=n;i++)
	{
		cin>>val[i];
		tot ^= val[i];
		siz[i] = 0;
		eg[i].clear();
	}
	int u, v;
	for(int i=2;i<=n;i++)
	{
		cin>> u >> v;
		eg[u].push_back(v);
		eg[v].push_back(u);
	}
	if(tot == 0) {cout<<"YES"<>_;while(_--)
	solve();return 0;
}