P4551 最长异或路径
其实我也不知道算不算数据结构，反正就是01trie，不过题目本身似乎也是一个模板？
https://www.luogu.com.cn/blog/108510/solution-p4551
（由于一看到异或就恐惧，所以就直接放看的题解了）
本质上难点就在于：
一个数，如果它两次异或同一个数，那么它是不会有改变的。
那么i~j的路径上的异或和，就可以表示成根到i的异或和异或上根到j的异或和。
#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
struct node{
int to;
int w;
int nex;
}a[2000001];
int hd[2000001];
int cnt;
void ru(int x,int y,int z)
{
a[++cnt].nex=hd[x];
a[cnt].to=y;
a[cnt].w=z;
hd[x]=cnt;
}
int sum[2000001];
void dfs(int x,int fa)
{
for(int i=hd[x];i;i=a[i].nex)
{
int v=a[i].to;
int w=a[i].w;
if(v==fa) continue;
sum[v]=sum[x]^w;
dfs(v,x);
}
}
struct node2{
int ch[2];
}t[2000001];
int tot;
void build(int v,int x)
{
for(int i=(1<<30);i;i>>=1)
{
bool c=v&i;
if(!t[x].ch[c])
{
t[x].ch[c]=++tot;
}
x=t[x].ch[c];
}
}
int cx(int v,int x)
{
int ans=0;
for(int i=(1<<30);i;i>>=1)
{
bool c=v&i;
if(t[x].ch[!c])
{
ans+=i;
x=t[x].ch[!c];
}
else x=t[x].ch[c];
}
return ans;
}
int main()
{
int n;
scanf("%d",&n);
int x,y,z;
for1(i,1,n-1)
{
scanf("%d%d%d",&x,&y,&z);
ru(x,y,z);
ru(y,x,z);
}
dfs(1,-1);
for1(i,1,n)build(sum[i],0);
int ans=0;
for1(i,1,n)
ans=max(ans,cx(sum[i],0));
printf("%d\n",ans);
}