题目传送门：http://poj.org/problem?id=3764

The xor-longest Path

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 9482		Accepted: 1932

Description

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:

$_{xor}length(p)=\oplus_{e \in p}w(e)$

⊕ 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? 　

Input

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.

Output

For each test case output the xor-length of the xor-longest path.

Sample Input

Sample Output

Hint

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

题目大意：

有一棵N个节点的树，求树上的最大路径异或和。

解题思路：

静态链接表存树。

我们要求一条最大异或和的路径，暴力太恐怖了。

这里巧妙地运用了公式 a ⊕ b ⊕ a = b，也就是说相同的路径被异或两次相当于没有被异或，那么我们从根节点开始 dfs 并且每到一个点就把该点到根节点的路径异或和丢进 01字典树里，然后每次都把当前边和 01字典树里匹配得到最大的异或值（因为在同一棵树，两节点间必定有一个公共祖先，所以起点终点必定是相连的），最后遍历完一棵树得到的最大异或值就是结果。

AC code：

 ///数组实现

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #define INF 0x3f3f3f3f

 #define LL long long int

 #define Bit 30

 using namespace std;

 const int MAXN = 1e5+;

 struct node{

     int to, va, next;

 }t[MAXN<<];

 int head[MAXN];

 int ch[MAXN*Bit][];

 int value[Bit*MAXN];

 //bool vis[MAXN];

 int node_cnt, edge_cnt;

 int N, ans;

 inline void init()

 {

     ans = ;

     node_cnt = ;

     edge_cnt = ;

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

     memset(ch[], , sizeof(ch[]));

    // memset(vis, false, sizeof(vis));

 }

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

 {

     t[edge_cnt].next = head[u];

     t[edge_cnt].to = v;

     t[edge_cnt].va = w;

     head[u] = edge_cnt++;

 }

 void Insert(int x)

 {

     int cur = ;

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

         int index = (x>>i)&;

         if(!ch[cur][index]){

             memset(ch[node_cnt], , sizeof(ch[node_cnt]));

             ch[cur][index] = node_cnt;

             value[node_cnt++] = ;

         }

     cur = ch[cur][index];

     }

     value[cur] = x;

 }

 int query(int x)

 {

     int cur = ;

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

     {

         int index = (x>>i)&;

         if(ch[cur][index^]) cur = ch[cur][index^];

         else cur = ch[cur][index];

     }

     return value[cur]^x;

 }

 void solve(int x,int fa, int res)

 {

     Insert(res);

     //vis[x] = true;

     for(int i = head[x]; i != -; i = t[i].next){

         int v = t[i].to;

         if(v == fa) continue;

         //if(!vis[v]){

         ans = max(ans, query(res^t[i].va));

         solve(v, x, res^t[i].va);

         //}

     }

 }

 int main()

 {

     int a, b, c;

     while(~scanf("%d", &N)){

         init();

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

             scanf("%d%d%d", &a, &b, &c);

             a++, b++;

             add_edge(a, b, c);

             add_edge(b ,a, c);

         }

         solve(, -, );

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

     }

     return ;

 }

巴特西

POJ 3764 The xor-longest Path 【01字典树&&求路径最大异或和&&YY】