In an edge-weighted tree, the xor-length of a path p is defined as the xor sum of the weights of edges on p:

⊕ is the xor operator.

We say a path the xor-longest path if it has the largest xor-length. Given an edge-weighted tree with n nodes, can you find the xor-longest path? 　

The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.

The xor-longest path is 0->1->2, which has length 7 (=3 ⊕ 4)

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=200010;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 struct edge{17     int v,nxt,w;18 }e[mxn<<1];19 int hd[mxn],mct=0;20 void add_edge(int u,int v,int w){21     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return;22 }23 int t[mxn*10][2],cnt=1;24 int n,ans=0;25 int f[mxn];26 void insert(int x){27     int now=1;28     for(int i=31;i>=0;i--){29         int v=(x>>i)&1;30         if(!t[now][v])t[now][v]=++cnt;31         now=t[now][v];32     }33     return;34 }35 void query(int x){36     int now=1;37     int res=0;38     for(int i=31;i>=0;i--){39         int v=(x>>i)&1;40         if(t[now][v^1]){41             v^=1;42             res+=(1<<i);43         }44         now=t[now][v];45     }46     ans=max(res,ans);47     return;48 }49 void DFS(int u,int fa,int num){50     f[u]=num;51     for(int i=hd[u];i;i=e[i].nxt){52         int v=e[i].v;53         if(v==fa)continue;54         DFS(v,u,num^e[i].w);55     }56     return;57 }58 void init(){59     memset(hd,0,sizeof hd);60     memset(t,0,sizeof t);61 //    memset(f,0,sizeof f);62     mct=0;cnt=1;ans=0;63     return;64 }65 int main(){66     while(scanf("%d",&n)!=EOF){67         init();68         int i,j,u,v,w;69         for(i=1;i<n;i++){70             u=read();v=read();w=read();71             u++;v++;72             add_edge(u,v,w);73             add_edge(v,u,w);74         }75         DFS(1,0,0);76         for(i=1;i<=n;i++){77 //            printf("f[%d]:%d\n",i,f[i]);78             query(f[i]);79             insert(f[i]);80         }81         printf("%d\n",ans);82     }83     return 0;84 }