poj3764字典树路径最大异或和

The xor-longest Path

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 6853		Accepted: 1464

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:

⊕ 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

4
0 1 3
1 2 4
1 3 6

Sample Output

7

Hint

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

先求出来到节点1的，然后字典树从高位到低位。异或和的性质以及贪心？。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+88;
int head[N],tot,sz,val[N];
struct node
{
    int v,next,w;
} e[N<<1];
struct Trie
{
    int next[2];
    void init()
    {
        memset(next,0,sizeof(next));
    }
} Ti[N*33];
void add(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].next=head[u];
    e[tot].w=w;
    head[u]=tot++;
    e[tot] .v=u;
    e[tot].next=head[v];
    e[tot].w=w;
    head[v]=tot++;
}
void Add(int x)
{
    int u=0,ind;
    for(int i=30; i>=0; --i)
    {
        if((1<<i)&x) ind=1;
        else ind=0;
        if(!Ti[u].next[ind])
        {
            Ti[u].next[ind]=++sz;
            Ti[sz].init();
        }
        u=Ti[u].next[ind];
    }
}
int get(int x)
{
    int u=0,num=0,ind;
    for(int i=30; i>=0; --i)
    {
        if((1<<i)&x) ind=0;
        else ind=1;
        if(Ti[u].next[ind])
        {
            u=Ti[u].next[ind];
            num|=(1<<i);
        }
        else u=Ti[u].next[!ind];
    }
    return num;
}
void dfs(int x,int v,int fa)
{
    val[x]=v;
    for(int i=head[x]; i+1; i=e[i].next)
    {
        int to=e[i].v;
        if(to==fa) continue;
        dfs(to,e[i].w^v,x);
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        tot=sz=0;
        int x,y,z;
        memset(head,-1,sizeof(head));
        for(int i=1; i<n; ++i)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x+1,y+1,z);
        }
        Ti[0].init();  //必须初始化
        dfs(1,0,0);
        int maxx=0;
        for(int i=1; i<=n; ++i)
        {
            maxx=max(maxx,get(val[i]));
            Add(val[i]);
        }
        printf("%d
",maxx);
    }
}