POJ 3764 The xor-longest Path （Trie树 + dfs）

题目原文：http://poj.org/PRoblem?id=3764

Description

In an edge-weighted tree, the xor-length of a pathp is defined as the xor sum of the weights of edges onp:

⊕ 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 integern(1<=n<=100000), The following n-1 lines each contains three integersu(0 <=u <n),v(0 <= v <n),w(0 <= w < 2^31), which means there is an edge between nodeu andv of lengthw.

Output

题目大意：给一颗有边权的树，求一条路径使得，这条路径上的所有边权异或值最大

解题思路：类比数组中求一段区间的和，我们可以用前缀和的思想先预处理出每个节点到根节点的异或前缀和，再有异或的性质可以得到，a^b^b = a，所以有任意两个节点之间的路径的异或和就可以用两个预处理的前缀来表示。公共祖先上面的路径的值会被重复计算两次而抵消。

       问题到这里就被简化为了另一个问题，在一组数中，求任意两个数的异或最大值，这是一个很经典的字典树问题。

没有做过的话，建议先做一下，可能对这道题目有所帮助。 例：HDU  4825

注意：本题对时间要求比较严格，所以需要使用字典树的数组式写法，我尝试的指针式写法TLE。

          加边的方式可以采用邻接表。 邻接表的头指针全部初始化为0作为截止条件，数组从1开始使用。

          dfs建树

AC代码：

/*    @Author: wchhlbt    @Date:   2017/3/5*///#include <bits/stdc++.h>#include <vector>#include <list>#include <map>#include <set>#include <queue>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <cstring>#include <limits>#include <climits>#include <cstdio>#define Fori(x) for(int i=0;i<x;i++)#define Forj(x) for(int j=0;j<x;j++)#define maxn 100005#define inf 0x3f3f3f3f#define ONES(x) __builtin_popcount(x)using namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> P;const double eps =1e-8;const int mod = 1000000007;const double PI = acos(-1.0);int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int n,x,q,e,cnt;ll a[maxn];ll ans;struct Edge{    int v,w,next;}edge[maxn<<1];int head[maxn];int vis[maxn];void add(int u,int v, int w)//邻接表方式加边{    edge[e].v = v; edge[e].w = w; edge[e].next = head[u]; head[u] = e++;    edge[e].v = u; edge[e].w = w; edge[e].next = head[v]; head[v] = e++;}//数组式写法的字典树struct Node{   int num;//记录每个单词出现的次数   int pNext[2];}node[maxn<<4];void Insert(ll x, int num){    int p = 0;   for(int i = 30; i>=0; i--){        int m = (x>>i)&1;       if (!node[p].pNext[m]) {           node[p].pNext[m] = ++cnt;           node[cnt].pNext[0] = node[cnt].pNext[1] = 0;       }       p = node[p].pNext[m];   }   node[p].num = num;}ll query(ll x){   int p = 0;   for(int i = 30; i>=0; i--){        int m = ((x>>i)&1)^1;        if(node[p].pNext[m])            p = node[p].pNext[m];        else            p = node[p].pNext[1-m];   }   return x^a[node[p].num];}void dfs(int u){    vis[u] = 1;    for(int i = head[u]; i; i = edge[i].next)    {        int v = edge[i].v; int w = edge[i].w;        if(vis[v])  continue;        a[v] = a[u]^w;        dfs(v);    }}int main(){    while(~scanf("%d",&n)){        ans = 0;        e = 1;cnt = 0;        node[0].pNext[0] = node[0].pNext[1] = 0;        memset(head,0,sizeof(head));        memset(vis, 0, sizeof(vis));        //memset(a,0,sizeof(a));//important        for(int i = 1; i<n; i++)        {            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            add(u,v,w);        }        dfs(0);        for(int i = 0; i<n; i++){//注意下标的对应            Insert(a[i], i);            ans = max(ans,query(a[i]));        }        printf("%I64d/n",ans);    }    return 0;}