D33 树上启发式合并 CF1709E XOR Tree

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> G[N]; 
int n, ans, a[N], dis[N]; //dis[x]从根到x的异或和
set<int> s[N]; //s[x]:x子树内各点的dis集合

void dfs(int x, int fa) 
{
	s[x].insert(dis[x]);
	bool flag=0;
	for(int y:G[x])if(y!=fa) 
	{
		dis[y]=dis[x]^a[y];
		dfs(y, x);

		if(s[x].size()<s[y].size()) swap(s[x], s[y]);
		//上面这一句就是启发式的体现，同时避免了MLE

		for(int z:s[y]) //如果s[x]中存在s[y]^a[x]
			if(s[x].find(z^a[x]) != s[x].end()) flag=1;
		for(int z:s[y]) s[x].insert(z); //s[y]并入s[x]
	}

	if(flag) ans++, s[x].clear(); //x子树已无贡献
}
int main() 
{
	scanf("%d", &n);for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	for(int i=1, x, y; i<n; i++) 
	{
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dis[1]=a[1];
	dfs(1, 0);
	printf("%d\n", ans);
	return 0;
}