BZOJ1954 Pku3764 The xor-longest Path

Description

给定一棵n个点的带权树,求树上最长的异或和路径. 

Input

第一行包含一个整数n(1≤n≤100000),下面的n-1行每行包含三个整数u(0≤u﹤n),v(0≤v﹤n),w(0≤w﹤n),表示节点u和v之间
的长度为w.

Output

输出最长异或和路径的长度.

Sample Input

4
1 2 3
2 3 4
2 4 6

Sample Output

7

Solution

首先定义key数组为每个点到根节点路径上的异或和,问题就转化成了求Max{key[i],key[j]}(i,j∈V).公共部分不影响结果,因为(a xor c)xor(b xor c)==a xor b.
然后把所有key按二进制位拆分,从高位到低位建成一棵Trie树,显然高位越大答案越大,每个节点贪心找一遍就可以了.

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
struct edge{
    int to,next,v;
}e[N*2];
int n,x,y,z,tot,cnt,ans;
int v[N],bin[50],c[N*35][2],key[N],head[N];
void add(int u,int v,int value){
    e[++tot]=(edge){v,head[u],value}; head[u]=tot;
}
void dfs(int u,int last){
    for (int i=head[u],v=e[i].to;i;i=e[i].next,v=e[i].to)
        if (v!=last){
            key[v]=key[u]^e[i].v;
            dfs(v,u);
        }
}
void insert(int x){
    int now=0;
    for (int i=30;i>=0;i--){
        int t=(x&bin[i])>0;
        if (!c[now][t]) c[now][t]=++cnt;
        now=c[now][t];
    }
}
int query(int x){
    int ans=0,now=0;
    for (int i=30;i>=0;i--){
        int t=(x&bin[i])>0;
        if (c[now][!t]) ans+=bin[i],now=c[now][!t];
        else now=c[now][t];
    }
    return ans;
}
int main(){
    bin[0]=1;
    for (int i=1;i<=30;i++)
        bin[i]=bin[i-1]<<1;
    scanf("%d",&n);
    for (int i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z); add(y,x,z);
    }
    dfs(1,0);
    for (int i=1;i<=n;i++)
        insert(key[i]);
    for (int i=1;i<=n;i++)
        ans=max(ans,query(key[i]));
    printf("%d",ans);
}