关于这题我写的启发式合并的复杂度

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=200005;
set<ll> s[N],tp;
ll n,val[N],ans;
struct node{
	ll nxt;
	ll to;
}e[N*2];
ll head[N],rx,ry,tot;
bool ok[N];
ll f[N],fx,fy,tmp;
inline void read(ll &x)
{
	ll f=1;char c;
	for(x=0,c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x*=f;
}
inline ll mx(ll _x,ll _y)
{
	return _x>_y?_x:_y;
}
inline ll mn(ll _x,ll _y)
{
	return _x<_y?_x:_y;
}
inline ll fd(ll x)
{
	return f[x]==x?x:f[x]=fd(f[x]);
}
inline void add(ll from,ll to)
{
	e[++tot].to=to;
	e[tot].nxt=head[from];
	head[from]=tot;
}
inline bool mergy(ll u,ll v,ll vl)
{
	bool rest=false;
	fx=fd(u);fy=fd(v);
	if(fx==fy) return false;
	if(s[fx].size()<s[fy].size()) swap(fx,fy);
	for(set<ll>::iterator it=s[fy].begin();it!=s[fy].end();++it)
	{
		tmp=(*it);
		if(s[fx].count(tmp^vl)) rest=true;
	}
	for(set<ll>::iterator it=s[fy].begin();it!=s[fy].end();++it)
	{
		tmp=(*it);
		s[fx].insert(tmp);
	}	
	s[fy].clear();f[fy]=fx;return rest;
}
inline void dfs(ll x,ll fa)
{
	bool isx=false;
	for(int i=head[x];i;i=e[i].nxt)
	{
		ll v=e[i].to;
		if(v==fa) continue;
		dfs(v,x);
		if(!ok[v]) isx|=mergy(x,v,val[x]);//启发式合并
	}
	ll id=fd(x);
	if(s[id].count(val[x])) isx=true;
	
	if(isx) 
	{
		ans++;
		ok[x]=true;
//		printf("P:%lld\n",x);
	}
	else
	{
		tp.clear();
		for(set<ll>::iterator it=s[id].begin();it!=s[id].end();++it)
				tp.insert((*it)^val[x]);
		s[id]=tp;
		s[id].insert(val[x]);
		tp.clear();//把这里的遍历改掉就过了
	}
	return ;
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++) 
	{ 
		read(val[i]);
		f[i]=i;
	}
	for(int i=1;i<n;i++)
	{
		read(rx);read(ry);
		add(rx,ry);add(ry,rx);
	}
	dfs(1,1);
	printf("%lld\n",ans);
	return 0;
}

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=200005;
set<ll> s[N];
ll n,a[N],val[N],ans; 
struct node{
	ll nxt;
	ll to;
}e[N*2];
ll head[N],rx,ry,tot;
bool ok[N];
ll f[N],fx,fy,tmp;
inline void read(ll &x)
{
	ll f=1;char c;
	for(x=0,c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x*=f;
}
inline ll mx(ll _x,ll _y)
{
	return _x>_y?_x:_y;
}
inline ll mn(ll _x,ll _y)
{
	return _x<_y?_x:_y;
}
inline ll fd(ll x)
{
	return f[x]==x?x:f[x]=fd(f[x]);
}
inline void add(ll from,ll to)
{
	e[++tot].to=to;
	e[tot].nxt=head[from];
	head[from]=tot;
}
inline bool mergy(ll u,ll v,ll vl)
{
	bool rest=false;
	fx=fd(u);fy=fd(v);
	if(fx==fy) return false;
	if(s[fx].size()<s[fy].size()) swap(fx,fy);
	for(set<ll>::iterator it=s[fy].begin();it!=s[fy].end();++it)
	{
		tmp=(*it);
		if(s[fx].count(tmp^vl)) rest=true;
	}
	for(set<ll>::iterator it=s[fy].begin();it!=s[fy].end();++it)
	{
		tmp=(*it);
		s[fx].insert(tmp);
	}	
	s[fy].clear();f[fy]=fx;return rest;
}
inline void dfs(ll x,ll fa)
{
	bool isx=false;
	for(int i=head[x];i;i=e[i].nxt)
	{
		ll v=e[i].to;
		if(v==fa) continue;
		dfs(v,x);
		if(!ok[v]) isx|=mergy(x,v,a[x]);
	}
	ll id=fd(x);
	if(s[id].count(val[x]^a[x])) isx=true;
	
	if(isx) 
	{
		ans++;
		ok[x]=true;
//		printf("P:%lld\n",x);
	}
	else{s[id].insert(val[x]);}//改变了val[x]含义，不用再次遍历修改
	return ;
}
inline void D(ll x,ll fa)
{
	for(int i=head[x];i;i=e[i].nxt)
	{
		ll v=e[i].to;
		if(v==fa) continue;
		val[v]=val[x]^a[v];
		D(v,x);
	}
	return ;
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++) 
	{ 
		read(a[i]);
		val[i]=a[i];
		f[i]=i;
	}
	for(int i=1;i<n;i++)
	{
		read(rx);read(ry);
		add(rx,ry);add(ry,rx);
	}
	D(1,1);
	dfs(1,1);
	printf("%lld\n",ans);
	return 0;
}