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:

$_{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)

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=2e5+;

int head[N],tot,sz,val[N];

struct node

{

    int v,next,w;

} e[N<<];

struct Trie

{

    int next[];

    void init()

    {

        memset(next,,sizeof(next));

    }

} Ti[N*];

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=,ind;

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

    {

        if((<<i)&x) ind=;

        else ind=;

        if(!Ti[u].next[ind])

        {

            Ti[u].next[ind]=++sz;

            Ti[sz].init();

        }

        u=Ti[u].next[ind];

    }

}

int get(int x)

{

    int u=,num=,ind;

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

    {

        if((<<i)&x) ind=;

        else ind=;

        if(Ti[u].next[ind])

        {

            u=Ti[u].next[ind];

            num|=(<<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+; 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=;

        int x,y,z;

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

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

        {

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

            add(x+,y+,z);

        }

        Ti[].init();  //必须初始化

        dfs(,,);

        int maxx=;

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

        {

            maxx=max(maxx,get(val[i]));

            Add(val[i]);

        }

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

    }

}

巴特西

poj3764字典树路径最大异或和

最新文章

热门文章