题目 POJ3764 The xor-longest Path
[原题传送门](http://poj.org/problem?id=3764)
主要思路：
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;
}