The xor-longest Path

时间：2023-03-08 20:48:26
The xor-longest Path
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 3875   Accepted: 850

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:

The xor-longest Path

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

　　這道題由於沒看到多組數據，WA了很久，題目比較簡單，但是運用了a xor b= a xor c xor b xor c，這應該是解異或題目常用的技巧。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<string>

#include<queue>

#include<stack>

using namespace std;

#ifdef WIN32

#define LL "%I64d"

#else

#define LL "%lld"

#endif

#define MAXN 110000

#define MAXV MAXN

#define MAXE MAXV*2

#define MAXT MAXN*200

//AC

typedef long long qword;

int n,m;

struct trie

{

        int ch[];

}tree[MAXT];

int toptr=;

inline void new_node(int &now)

{

        now=++toptr;

        tree[now].ch[]=tree[now].ch[]=;

}

int dbg=;

void build_trie(qword x)

{

        dbg++;

        int now=;

        int i;

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

        {

                if (!tree[now].ch[(x&(1ll<<i))!=])

                {

                        new_node(tree[now].ch[(x&(1ll<<i))!=]);

                }

                now=tree[now].ch[(x&(1ll<<i))!=];

        }

        if (dbg==)

                dbg--;

}

struct Edge

{

        int np;

        qword val;

        Edge *next;

}E[MAXE],*V[MAXV];

int tope=-;

void addedge(int x,int y,qword z)

{

        E[++tope].np=y;

        E[tope].val=z;

        E[tope].next=V[x];

        V[x]=&E[tope];

}

int fa[MAXN],depth[MAXN],val[MAXN];

void dfs(int now,int v)

{

        Edge *ne;

        build_trie(v);

        val[now]=v;

        for (ne=V[now];ne;ne=ne->next)

        {

                if (ne->np==fa[now])continue;

                fa[ne->np]=now;

                dfs(ne->np,v^ne->val);

        }

}

qword find(qword x)

{

        int now=;

        int ret=;

        int i;

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

        {

                if (tree[now].ch[(x&(1ll<<i))==])

                {

                        now=tree[now].ch[(x&(1ll<<i))==];

                        ret+=1ll<<i;

                }else

                {

                        now=tree[now].ch[(x&(1ll<<i))!=];

                }

        }

        if (!now)throw ;

        return ret;

}

int main()

{

        freopen("input.txt","r",stdin);

        //freopen("output.txt","w",stdout);

        int i,j,k;

        qword x,y,z;

        while (~scanf("%d",&n))

        {

                memset(V,,sizeof(V));

                memset(fa,-,sizeof(fa));

                toptr=;

                tope=-;

                tree[].ch[]=tree[].ch[]=;

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

                {

                        scanf(LL LL LL,&x,&y,&z);

                        addedge(x,y,z);

                        addedge(y,x,z);

                }

                fa[]=;

                dfs(,);

                qword ans=;

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

                {

                        ans=max(ans,find(val[i]));

                }

                printf(LL "\n",ans);

        }

        return ;

}

相关文章