Poj3764---The xor-longest Path

传送门：http://poj.org/problem?id=3764

题解

注意到：对于任意一条路径的异或，表示为f(u, v) 则f(u, v) = f(1, u) ^ f(1, v)
接下来就很简单了，就是在一个数组内，找两个数异或值最大（该模型具体实现见：https://www.cnblogs.com/wangyh1008/p/9401389.html ）

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N=1750005;
int vet[N],next[N],head[N],dis[N],x[N],edgenum,ch[N][5],tot,n;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}
inline void init()
{
    memset(ch,0,sizeof(ch)); memset(x,0,sizeof(x)); tot=1; edgenum=0;
    memset(head,-1,sizeof(head)); memset(next,-1,sizeof(next));
}
inline void addedge(int u,int v,int t)
{
    vet[++edgenum]=v;
    next[edgenum]=head[u];
    head[u]=edgenum;
    dis[edgenum]=t;
}
void dfs(int u)
{
    for (int e=head[u]; e!=-1; e=next[e])
        if (!x[vet[e]] && vet[e]!=1){
            int v=vet[e];
            x[v]=x[u]^dis[e];
            dfs(v);
        }
}
inline void insert(int x)
{
    int u=1;
    for (int i=1<<30; i; i>>=1){
        int c=x&i; if (c) c=1; else c=0;
        if (!ch[u][c]) ch[u][c]=++tot;
        u=ch[u][c];
    }
}
inline int get(int x)
{
    int u=1,ans=0;
    for (int i=1<<30; i; i>>=1){
        int c=x&i; if (c) c=0; else c=1;
        if (ch[u][c]) ans+=i,u=ch[u][c]; else u=ch[u][!c];
    }
    return ans;
}
int main()
{
    while (~scanf("%d",&n)){
        init();
        for (int i=1; i<n; i++){
            int x=read(),y=read(),v=read(); x++; y++;
            addedge(x,y,v); addedge(y,x,v);
        }
        dfs(1);
        for (int i=1; i<=n; i++) insert(x[i]);
        int ans=0;
        for (int i=1; i<=n; i++) ans=max(ans,get(x[i]));
        printf("%d\n",ans);
    }
    return 0;
}