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 uand v of length w.

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

 #include <iostream>

 #include <set>

 #include <cmath>

 #include <stdio.h>

 #include <cstring>

 #include <algorithm>

 #include <map>

 using namespace std;

 typedef long long LL;

 #define inf 0x7f7f7f7f

 int n;

 const int maxn = 1e5 + ;

 struct edge{

     int v, w;

     int nxt;

 }e[maxn * ];

 int head[maxn], tot = ;

 int xordis[maxn];

 int trie[maxn *  + ][], treetot = ;

 void addedge(int u, int v, int w)

 {

     e[tot].v = v;

     e[tot].w = w;

     e[tot].nxt = head[u];

     head[u] = tot++;

     e[tot].v = u;

     e[tot].w = w;

     e[tot].nxt = head[v];

     head[v] = tot++;

 }

 void dfs(int rt, int fa)

 {

     for(int i = head[rt]; i != -; i = e[i].nxt){

         int v = e[i].v;

         if(v == fa)continue;

         xordis[v] = xordis[rt] ^ e[i].w;

         dfs(v, rt);

     }

 }

 void init()

 {

     memset(head, -, sizeof(head));

     tot = ;

     memset(xordis, , sizeof(xordis));

     memset(trie, , sizeof(trie));

 }

 void insertt(int x)

 {

     int p = ;

     for(int i = ; i >= ; i--){

         int ch = x >> i & ;

         if(trie[p][ch] == ){

             trie[p][ch] = ++tot;

         }

         p = trie[p][ch];

     }

 }

 int searchh(int x)

 {

     int p = , ans = ;

     for(int i = ; i >= ; i--){

         int ch = x >> i & ;

         if(trie[p][ch ^ ]){

             p = trie[p][ch ^ ];

             ans |=  << i;

         }

         else{

             p = trie[p][ch];

         }

     }

     return ans;

 }

 int main()

 {

     while(scanf("%d", &n) != EOF){

         init();

         for(int i = ; i < n - ; i++){

             int u, v, w;

             scanf("%d%d%d", &u, &v, &w);

             addedge(u, v, w);

         }

         dfs(, -);

         /*for(int i = 0; i < n; i++){

             printf("%d\n", xordis[i]);

         }*/

         int ans = ;

         for(int i = ; i < n; i++){

             insertt(xordis[i]);

             //cout<<searchh(xordis[i])<<endl;

             ans = max(ans, searchh(xordis[i]));

             ans = max(ans, xordis[i]);

         }

         printf("%d\n", ans);

     }

     return ;

 }