调了一天死活 TLE 第七个点，自己造1e5的数据最快4s最慢7s，怀疑是启发式合并写假了，求调。

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int t,n,a[N],p[N],cnts,f[N],son[N],sz[N];
struct edge{
	int v,nxt;
}e[N<<1];
int head[N],cnte;
void adde(int u,int v){
	e[++cnte]=edge{v,head[u]};head[u]=cnte;
}
void dfs0(int x,int fa){
	sz[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		dfs0(v,x);
		sz[x]+=sz[v];
		if(sz[v]>sz[son[x]]) son[x]=v;
	}
}
set<int> s[N];
void allxor(int x,int a){
	set<int> ss;
	for(auto i:s[x]){
		ss.insert(i^a);
	}
	s[x]=ss;
}
void merge(map<int,int> &mp,int x,int y){
	if(s[p[x]].size()<s[p[y]].size()){
		swap(p[x],p[y]);
	}
	for(auto i:s[p[y]]){
		if(s[p[x]].count(i)){
			mp[i]++;
		}else{
			s[p[x]].insert(i);
		}
	}
}
int mx1;map<int,int> mp1;
void dfs(int x,int fa){
	if(sz[x]==1){
		p[x]=++cnts;
		s[p[x]].insert(a[x]);
		return;
	}
	dfs(son[x],x);
	p[x]=p[son[x]];
	map<int,int> mp;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa||v==son[x]) continue;
		dfs(v,x);
		f[x]+=f[v];
		merge(mp,x,v);
		s[p[v]].clear();
	}
	allxor(p[x],a[x]);
	int mx=0;
	for(auto i:mp){
		mx=max(mx,i.second);
	}
	if(x==1){
		mx1=mx;mp1=mp;
	}
	f[x]+=s[p[x]].size();
	for(auto i:mp){
		if(i.second!=mx){
			f[x]+=i.second;
			s[p[x]].erase(i.first^a[x]);
		}else{
			f[x]+=mx;
		}
	}
	f[x]-=mx+1;
	mp.clear();
}
signed main(){
	freopen("in.in","r",stdin);
	n=read();
	forup(i,1,n){
		a[i]=read();
	}
	forup(i,1,n-1){
		int u=read(),v=read();
		adde(u,v);adde(v,u);
	}
	dfs0(1,0);
	dfs(1,0);
//	for(auto i:s[p[1]]){
//		printf("%d ",i);
//	}
//	puts("");
	if((!mx1&&s[p[1]].count(0))||(mx1&&mp1[0^a[1]]==mx1)) printf("%d",f[1]);
	else printf("%d",f[1]+1);
}