萌新求助时间复杂度

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n,res,v[N],id[N],delta[N];
int h[N],e[N<<1],ne[N<<1],idx;
map<int,int> M[N];
inline void add(int a,int b)
{
	e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
inline void dp(int u,int fa)
{
	id[u]=u;
	if(u!=1&&ne[h[u]]==-1) return M[id[u]][v[u]]++,void();
	int mx=1,cnt=0;
	for(int i=h[u];~i;i=ne[i])
	{
		if(e[i]==fa) continue;
		cnt++;v[e[i]]^=v[u];
		dp(e[i],u);
		if(M[id[u]].size()<M[id[e[i]]].size()) swap(id[u],id[e[i]]);
		for(auto x:M[id[e[i]]]) M[id[u]][x.first]+=x.second,mx=max(mx,M[id[u]][x.first]);
	}
	res+=cnt-mx;
	map<int,int> T;
	for(auto x:M[id[u]]) if(x.second==mx) T[x.first]++;
	swap(M[id[u]],T);
}
int main()
{
	memset(h,-1,sizeof h);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&v[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dp(1,1);
	printf("%d",res+!M[id[1]][0]);
	return 0;	
}