写的 dsu+trie，现在状态是 TLE on #40，不知道哪里还能优化了/kel

#pragma GCC optimize("Ofast")
#include<cstdio>
int hed[300001],net[600001],ver[600001],tot;
void add(int x,int y){
	ver[++tot]=y;
	net[tot]=hed[x];
	hed[x]=tot;
}
int trie[18000001][2],cnt,root[300001],n;
int sz[300001],a[300001],dis[300001];
int son[300001],se[18000001];
//se 记录的是 trie 树中的 size，sz 与 son 是原树 dsu 用的重儿子。
bool ndc[300001];
// 点 x 是否要被修理
void insert(int id,int val){
	if(!root[id])root[id]=++cnt;
	int pos=root[id],i;
	for(i=29;i>=0;i--){
		se[pos]++;
		int x=((val&(1<<i))!=0);
		if(!trie[pos][x])trie[pos][x]=++cnt;
		pos=trie[pos][x];
	}
	se[pos]++;
}
bool fxor(int id,int val){
	//寻找有无 xor 值相同的
	int pos=root[id],i;
	for(i=29;i>=0;i--){
		int x=((val&(1<<i))!=0);
		if(!trie[pos][x])return 0;
		pos=trie[pos][x];
	}
	return 1;
}
int qval(int id,int rk){
	//查询第 k 大，没有返回 -1
	//唯一作用是 dsu 的时候获取被暴力合并的子树的有用权值
	int pos=root[id],i,val=0;
	if(rk>se[pos])return -1;
	for(i=29;i>=0;i--){
		if(se[trie[pos][0]]>=rk)pos=trie[pos][0];
		else rk-=se[trie[pos][0]],pos=trie[pos][1],val+=1<<i;
	}
	return val;
}
void dfs0(int x,int fr){
	//剖出重儿子并处理出 dis
	int i;
	sz[x]=1;
	dis[x]^=a[x];
	for(i=hed[x];i;i=net[i]){
		int y=ver[i];
		if(y==fr)continue;
		dis[y]=dis[x];
		dfs0(y,x);
		sz[x]+=sz[y];
		if(sz[y]>sz[son[x]])son[x]=y;
	}
}
void dfs1(int x,int fr){
	//找答案
	int i,j;
	if(!son[x]){
		insert(x,dis[x]);
		return;
	}
	dfs1(son[x],x);
	if(!ndc[son[x]])root[x]=root[son[x]];
	//如果重儿子需要修改就不用管，否则直接继承
	for(i=hed[x];i;i=net[i]){
		int y=ver[i];
		if(y==fr||y==son[x])continue;
		dfs1(y,x);
		if(ndc[y]||ndc[x])continue;
		for(j=1;j<=n;j++){
			int val=qval(y,j);
			//提取出合并上去的树的每个权值更新答案。
			if(val==-1)break;
			if(fxor(x,val^a[x])){
				ndc[x]=1;
				break;
			}
		}
		if(ndc[x])continue;
		for(j=1;j<=n;j++){
			int val=qval(y,j);
			if(val==-1)break;
			insert(x,val);
		}
		//把子树的值插进来
	}
	if(fxor(x,dis[x]^a[x]))ndc[x]=1;
	else insert(x,dis[x]);
}
int main(){
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs0(1,1);
	dfs1(1,1);
	int res=0;
	for(i=1;i<=n;i++)res+=ndc[i];
	printf("%d",res);
}