【poj3764】The xor-longest Path

The xor-longest Path

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)

题意：

给你一棵树，求树上异或和最大的路径。

题解：

这题之前索神讲过……所以我竟然还考虑了一会才写

首先看到异或我们不妨顺便总结一下它的性质：

自反性：x^0=x, x^x=0
结合性：a^b^c=a^(b^c)

由这两个性质能组合出一个在OI中常用的技巧：a^b^a^c=b^c

也就是说两段相同的东西（可以是前缀，后缀，区间）异或起来就消掉了。

知道这个性质之后我们还知道一个模型：

对于一个数，想要在$n$个数中找到与它异或和最大的数，我们除了暴力，

也可以将每个数拆成二进制后视作一个字符串建立Trie树，这样就可以做到O(logn)查询。

那么我们再来看一下这道题：树上路径由于有多个点所以不能应用上面的方法。

这个时候应用第一个技巧我们可以发现：Sum(u,v)=Sum(1,u)^Sum(1,v)

那么多个点的路径异或和就转化成了两个点的前缀异或和。

然后直接写就好了。

代码：

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define MAXN 100005

#define MAXM 500005

#define INF 0x7fffffff

#define ll long long

inline int read(){

    int x=,f=;

    char c=getchar();

    for(;!isdigit(c);c=getchar())

        if(c=='-')

            f=-;

    for(;isdigit(c);c=getchar())

        x=x*+c-'';

    return x*f;

}

int N,cnt,hd[MAXN],cst[MAXM<<];

int to[MAXM<<],nxt[MAXM<<];

int num=,sum[MAXN],ch[MAXN*][];

inline void addedge(int u,int v,int w){

    to[++cnt]=v,cst[cnt]=w,nxt[cnt]=hd[u],hd[u]=cnt;

    to[++cnt]=u,cst[cnt]=w,nxt[cnt]=hd[v],hd[v]=cnt;

}

inline void insert(int x){

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

        bool c=(x&(<<i))!=;

        if(!ch[u][c]) ch[u][c]=++num;

        u=ch[u][c];

    }

}

inline void dfs(int u,int fa,int s){

    sum[u]=s; insert(s);

    for(int i=hd[u];i;i=nxt[i]){

        int v=to[i],w=cst[i];

        if(v==fa) continue;

        dfs(v,u,s^w);

    }

    return;

}

inline int calc(int x){

    int ans=,u=;

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

        bool c=(x&(<<i))!=;

        if(ch[u][c^]) ans+=(<<i),u=ch[u][c^];

        else u=ch[u][c];

    }

    return ans;

}

int main(){

    N=read(); int ans=;

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

        int u=read(),v=read(),w=read();

        addedge(u,v,w);

    }

    dfs(,,);

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

        ans=max(ans,calc(sum[i]));

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

    return ;

}

巴特西

【poj3764】The xor-longest Path

The xor-longest Path

题意：

题解：

代码：

最新文章

热门文章