题解 POJ3764

• 题目 POJ3764 The xor-longest Path 原题传送门

• 主要思路：

1. 求出每个点到根节点（这里是树，所以直接取0）路径上所有权值xor和为d[i],则任意两点间路径xor和则为 d[x]^d[y]（至于证明，作者太懒，不想写）

2. 接着用trie树跑出 max(d[x]^d[y]) (0<=x<n && 0<=y<n)

• Code

#include<cstdio>
#include<cstring>
//#include<windows.h>
using namespace std;
#define rg register int
#define I inline int
#define V inline void
#define ll long long
#define db double
#define B inline bool
#define F1(i,a,b) for(rg i=a;i<=b;++i)
#define F2(i,a,b) for(rg i=a;i>=b;--i)
#define ed putchar('\n')
#define bl putchar(' ')
#define Max(a,b) ((a)>(b)?(a):(b))  
#define Min(a,b) ((a)<(b)?(a):(b)) 
//#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
const int N=100005;
template<typename TP>V read(TP &x)
{
    TP f=1;x=0;register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
    x*=f;
}
template<typename TP>V print(TP x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,a,b,c,ans,cnt=1,t[N<<5][2];
struct node{
    int v,w,nxt;
}e[N<<1];
int tot,h[N],d[N];
template<typename TP>V add(TP u,TP v,TP w)
{
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nxt=h[u];
    h[u]=tot;
}
template<typename TP>V dfs(TP x,TP fa)
{
//    print(d[x]),system("pause"),ed;
    for(TP i=h[x];i;i=e[i].nxt)
    {
        TP v=e[i].v,w=e[i].w;
        if(v==fa) continue;
        d[v]=d[x]^w;
        dfs(v,x);
    }
}
struct T{
    template<typename TP>V insert(TP val)
    {
        TP rt=1;
        F2(i,30,0)
        {
            TP id=val>>i&1;
            if(!t[rt][id]) t[rt][id]=++cnt;
            rt=t[rt][id];
        }
    }
    template<typename TP>I search(TP val)
    {
        TP rt=1,sum=0;
        F2(i,30,0)
        {
            TP id=val>>i&1;
            if(t[rt][id^1]) rt=t[rt][id^1],sum|=1<<i;
            else rt=t[rt][id];
        }
        return sum;
    }
}trie;
V init()
{
    ans=tot=0,cnt=1;
    memset(h,0,sizeof h);
    memset(t,0,sizeof t);
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        F1(i,1,n-1)
        {
            read(a),read(b),read(c);
            add(a,b,c),add(b,a,c);
        }
        d[0]=0,dfs(0,-1);
        F1(i,0,n-1)
        {
            trie.insert(d[i]);
            ans=Max(ans,trie.search(d[i]));
        }
        print(ans),ed;
//        F1(i,0,n-1) print(d[i]),bl;
    }
    return 0;
}