题目大意：一棵树，边有权值。现在定义路径的值为路径中边的权值的异或值，求异或值最大的路径。
题解：
从a到b路径的异或值=a到根结点的异或值^b到根结点的异或值。
这样求出每个点到根结点的异或值，然后从n个数中选出异或值最大的数就可以。
把n个数插入Trie树中做。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100001+10; const int M=3000000+10; int n; int cnt; int sumedge; int head[N]; int a[N]; int t[M][2]; int ans; struct Edge { int x,y,z,nxt; Edge(int x=0,int y=0,int z=0,int nxt=0): x(x),y(y),z(z),nxt(nxt){} }edge[N<<1]; void add(int x,int y,int z) { edge[++sumedge]=Edge(x,y,z,head[x]); head[x]=sumedge; } void insert(int x) { int p=0; for(int i=30;~i;i--) { int s=(x>>i)&1; if(!t[p][s]) t[p][s]=++cnt; p=t[p][s]; } } void dfs(int now,int fa) { for(int i=head[now];i;i=edge[i].nxt) { int v=edge[i].y; if(v==fa) continue; a[v]=a[now]^edge[i].z; insert(a[v]); dfs(v,now); } } int slove(int x) { int res=0; int p=0; for(int i=30;~i;i--) { int s=(x>>i)&1; if(t[p][!s]) { res=res+(1<<i); p=t[p][!s]; }else p=t[p][s]; } return res; } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(0,-1); // for(int i=0;i<n;i++) cout<<"--"<<a[i]<<endl; for(int i=0;i<n;i++) { ans=max(ans,slove(a[i])); } cout<<ans; return 0;}