求助 蒟蒻刚学trie 悬关

#include<bits/stdc++.h>
using namespace std;
int n,value[100005],root,f[100005][35],cnt,ans,maxx;
vector<int> a[100005];
struct POINT { int son[2]; } q[100005];
void dfs(int x)
{
	for(register int i=0;i<a[x].size();++i)
	{
		value[a[x][i]]=value[a[x][i]]^value[x];
		dfs(a[x][i]);
	}
}
void push(int x)
{
	int last=0;
	for(register int i=1;i<=30;++i)
	{
		if(q[last].son[f[x][i]]==0) q[last].son[f[x][i]]=++cnt;
		last=q[last].son[f[x][i]];
	}
}
void find(int x,int y,int i)//第i个点 正在找第x位了
{
//	cout<<x<<" "<<y<<" "<<i<<" "<<f[i][x]<<" ";
//	cout<<q[y].son[0]<<" "<<q[y].son[1]<<" "<<ans<<" ";
	if(x==31) return;
	if(q[y].son[1-f[i][x]]!=0) { ans+=(long long)pow(2,30-x),find(x+1,q[y].son[1-f[i][x]],i); }
	else { find(x+1,q[y].son[f[i][x]],i); }
} 
//void print(int x)
//{
//	cout<<x<<endl;
//	if(q[x].son[0]!=0) { cout<<x<<" 0 "; print(q[x].son[0]);	}
//	if(q[x].son[1]!=0) { cout<<x<<" 1 "; print(q[x].son[1]);	}
//}
int main()
{
	cin>>n;
	for(register int i=1;i<n;++i)
	{
		int u,v,w;
		cin>>u>>v>>w;
		a[u].push_back(v); value[v]=w;
	}
	for(register int i=1;i<=n;++i)
		if(value[i]==0) { root=i; break; }
	dfs(root);
	for(register int i=1;i<=n;++i)
	{
		int t=0;maxx=max(maxx,value[i]);
		while(value[i]>0)
			f[i][30-t]=value[i]%2,value[i]/=2,t++;
	}
//	for(register int i=1;i<=n;++i)
//	{
//		for(register int j=1;j<=30;++j)
//			cout<<f[i][j]<<" ";
//		cout<<endl;
//	}
	for(register int i=1;i<=n;++i)
	{
		if(i==root) continue;
		push(i);
	}
	for(register int i=1;i<=n;++i)
	{
		if(i==root) continue;
		ans=0; find(1,0,i);
		maxx=max(maxx,ans);
//		cout<<endl<<ans<<endl;
	}
	cout<<maxx;
//	print(root);
	return 0;
}
/*
6
1 2 7
2 5 1
1 3 8
3 4 10
3 6 14
*/