链接：https://ac.nowcoder.com/acm/contest/201/D?&headNav=www
思路：题目要求的是每个等级下的最大 简单路径中的最大异或值，那么我们为了保证目前的路径中最大的权值
为当前访问的边，先进行排序，然后一条一条的插入边，并查集维护 各个联通块，启发式合并，由当前边连接起来的
两个联通块，所谓启发式合并也就是 把小的块 合并到大的上。然后 查询的时候就是再当前 这条边的两个联通块中
找一个包含此边的 最大异或路径， 为了方便处理 我们可以把每个点 存储一个到 它并查集根节点的 异或值，
这样进行 0 1 字典树维护即可。
#include<bits/stdc++.h>
using namespace std;
#define maxn 234567
vector<int>gra[maxn];
int tree[maxn*100][3],ans[maxn];
int n,m,u,v,w,root[maxn],tx,ty;
int fa[maxn],val[maxn],tot,sz[maxn];
struct node
{
int x,y,w;
bool operator<(const node &b)const
{
return w<b.w;
}
} edge[maxn];
int fond(int x)
{
return x==fa[x]?x:fa[x]=fond(fa[x]);
}
void updata(int x,int ad)
{
for(int i=20; i>=0; i--)
{
int id=((1<<i)&ad)?1:0;
if(!tree[x][id])
tree[x][id]=++tot;
x=tree[x][id];
}
}
int query(int x,int ad)
{
int ret=0;
for(int i=20; i>=0; i--)
{
int id=((1<<i)&ad)?1:0;
if(tree[x][id^1])
{
x=tree[x][id^1];
ret|=(1<<i);
}
else x=tree[x][id];
}
return ret;
}
int main()
{
scanf("%d",&n);
for(int i=1; i<n; i++)
{
scanf("%d%d%d",&u,&v,&w);
edge[i]=(node{u,v,w});
}
sort(edge+1,edge+n);
for(int i=1; i<=n; i++)
{
fa[i]=i;
sz[i]=1;
gra[i].push_back(i);
root[i]=++tot;
updata(root[i],0);
}
for(int i=1; i<n; i++)
{
u=edge[i].x,tx=fond(u);
v=edge[i].y,ty=fond(v);
w=(edge[i].w^val[u]^val[v]);
if(sz[tx]>sz[ty])swap(tx,ty),swap(u,v);
for(int j=0; j<sz[tx]; j++)
ans[i]=max(ans[i],query(root[ty],(w^val[gra[tx][j]])));
for(int j=0; j<sz[tx]; j++)
{
val[gra[tx][j]]^=w;
gra[ty].push_back(gra[tx][j]);
updata(root[ty],val[gra[tx][j]]);
}
fa[tx]=ty;
sz[ty]+=sz[tx];
}
for(int i=1; i<n; i++)
{
printf("%d",ans[i]);
if(i!=n-1)printf(" ");
else printf("
");
}
return 0;
}