【问题描述】
给你一棵树，n个节点，n-1条边每条边i都有一个权值wi。定义任意两点间的权值为：这两点间的路径上的所有边的值的异或。比如a点和b点间有i，j，k三条边，那么ab两点间的权值为：wi^wj^wk。求这个最大的权值（最长异或路径）。
【输入格式】
第一行为n表示节点数目（节点编号为1..n）。 接下来的n-1行，每行三个整数：u v w，表示一条树边(x,y)的权值为w（0<=w<2^31）。
【输出格式】
输出最长异或路径长度。
【输入样例】
4 1 2 3 2 3 4 2 4 6
【输出样例】
【样例解释】
The xor-longest path is 0->1->2, which has length 7 (=3 ⊕ 4)
【数据范围】
n<=250000
【来源】
poj 3764
这道题都能想到用dfs来生成根到每一个点的异或路径，但生成之后的操作就是重点了。 首先我们可以很容易的想到任意2个点直接的异或路径就是他们到跟的异或路径的异或值，证明如下： 设2点为x，y，公共祖先是z。z到根的异或路径是c,x到z的异或路径是a,y到z的异或路径是b。可得a^b=a^c^b^c。 不用二进制trie树的话很容易想到一个n^2时间复杂的算法，就是每2个数进行异或。但如果有了二进制trie树就可以先生成树，在再树上贪心的进行查找，很容易就可以得到最大值了，时间复杂度（n*log2n）。
#include<cstdlib> #include<cstdio> #include<cstring> #include<iostream> #include<vector> using namespace std; const int maxn=250005; struct edge { int u,v,w,next; }e[maxn]; int d[maxn],f[maxn]={0},ch[maxn*33][2]={0},cnt=0,tot=0,n; int a[33]; bool vis[maxn*33]={0},usd[maxn]={0}; void in(int x) { int k=30,p=0,d; while(k>=0) { if(x&a[k]) d=1; else d=0; if(!ch[p][d]) ch[p][d]=++cnt; p=ch[p][d]; k--; } vis[p]=1; } void add(int u,int v,int w) { e[++tot]=(edge){u,v,w,f[u]};f[u]=tot; } int read() { int x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x; } void dfs(int i) { for(int k=f[i];k;k=e[k].next) { int j=e[k].v,c=e[k].w; d[j]=d[i]^c; in(d[j]); dfs(j); } } int find(int x) { int k=30,p=0,d,y=0; while(k>=0) { if(x&a[k]) d=0; else d=1; if(!ch[p][d]) d=d^1; if(d) x^=a[k]; p=ch[p][d]; k--; } return x; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); n=read(); a[0]=1; for(int i=1;i<=30;i++) a[i]=a[i-1]*2; int x,y,w; for(int i=1;i<n;i++) { x=read();y=read();w=read(); add(x,y,w); usd[y]=1; } in(0); for(int i=1;i<=n;i++)if(!usd[i]) dfs(i); int ans=0; for(int i=1;i<=n;i++) ans=max(ans,find(d[i])); cout<<ans; return 0; }