The xor-longest Path

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 7332		Accepted: 1555

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.

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

4

0 1 3

1 2 4

1 3 6

7

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

//预处理出来每个点到根的异或值sxor，然后u,v之间的异或路径值就是sxor[u]^sxor[v],lca就消去了。然后把每个点的sxor值插入字典

//树（二进制字典树），枚举每个点贪心的找他的最大异或路径。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN=;

int head[MAXN*+],tot,sxor[MAXN*+],sz,nod[MAXN*+][],ans;

struct Edge

{

    int to,w,next;

}edge[MAXN*+];

void init()

{

    memset(sxor,,sizeof(sxor));

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

    nod[][]=nod[][]=;

    tot=;

    sz=;ans=;

}

void add(int x,int y,int z)

{

    edge[tot].to=y;

    edge[tot].w=z;

    edge[tot].next=head[x];

    head[x]=tot++;

    edge[tot].to=x;

    edge[tot].w=z;

    edge[tot].next=head[y];

    head[y]=tot++;

}

void insert(int x)

{

    int rt=;

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

        int id=(x>>i)&;

        if(nod[rt][id]==){

            nod[rt][id]=++sz;

            nod[sz][]=nod[sz][]=;

        }

        rt=nod[rt][id];

    }

}

void dfs(int x,int fa,int sum)

{

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

        int y=edge[i].to;

        if(y==fa) continue;

        sxor[y]=(sum^edge[i].w);

        dfs(y,x,sum^edge[i].w);

    }

}

void solve(int x)

{

    int sum=,rt=;

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

        int id=(x>>i)&;

        if(nod[rt][!id]){

            sum|=(<<i);

            rt=nod[rt][!id];

        }else if(nod[rt][id]) rt=nod[rt][id];

        else break;

    }

    ans=max(ans,sum);

}

int main()

{

    int n;

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

        int x,y,z;

        init();

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

            scanf("%d%d%d",&x,&y,&z);

            add(x,y,z);

        }

        dfs(,-,);

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

            solve(sxor[i]);

            insert(sxor[i]);

        }

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

    }

    return ;

}