cf1709E. XOR Tree（启发式合并入门）

cf1709E. XOR Tree
贪心是显然的，关键是如何合并两棵子树的信息，可以采用启发式合并。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<unordered_map>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=2e5+5;
int n,a[N],x,y,b[N];
int head[N],to[N*2],nex[N*2],tot,ans;
set<int> c[N];
void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
	b[x]^=a[x];
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		b[v]^=b[x];
		dfs(v,x);
	}
}
void calc(int x,int y){
	c[x].insert(b[x]);
	bool flag=0;
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		calc(v,x);
		
		if (c[x].size() < c[v].size()) c[x].swap(c[v]);
		for (auto j:c[v]) {
			if (c[x].find(j^a[x])!=c[x].end()) {  
				flag=1;
			}
		}
		
		for (auto j:c[v]) {
			c[x].insert(j);
		}
	}
	
	if (flag) {
		ans++;
		c[x].clear();
	}
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);

	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]);
	fo(i,1,n-1) {
		scanf("%d %d",&x,&y);
		add(x,y); add(y,x);
	}

	dfs(1,0);
	
	calc(1,0);
	
	printf("%d",ans);
	
	return 0;
}