题目链接：http://poj.org/problem?id=3764
我们可以在O(32*n）时间内求出一个长度为n的序列中取两个数的最大异或，而树中的异或有如下公式：path[x]=path(root,x) xor path(root,y)，所以处理出path(root,i)之后就简化成了
简单问题，处理方式是dfs，有公式：path[x]=path(x->father,x) xor path(root,x->father).
注意边是无方向的，数组大小开合适。
代码：
#include<iostream> #include<cstdio> #include<string.h> using namespace std; #define maxn 100010 int trie[maxn*33][2],head[maxn],e[maxn*2],len[maxn*2],nxt[maxn*2]; int num=0,tot=0,n;//e中保存的是边的右端点 num为边的编号 int d[maxn];//根节点到i点的异或和 bool v[maxn]; void addedge(int u,int v,int w){ e[++num]=v; len[num]=w; nxt[num]=head[u]; head[u]=num; } void dfs(int x){ for(int i=head[x];i;i=nxt[i]){ int to=e[i],weight=len[i]; if(v[to])continue; v[to]=true; d[to]=d[x]^weight;//有公式：d[x]=d[x->father] xor x->weight dfs(to); } } void insert(int x){ int p=0; for(int i=31;i>=0;i--){ int tmp=(x>>i)&1; if(!trie[p][tmp])trie[p][tmp]=++tot; p=trie[p][tmp]; } } int search(int x){ int ans=0,p=0; for(int i=31;i>=0;i--){ int tmp=(x>>i)&1; if(trie[p][tmp^1]){ ans=(ans<<1)+(tmp^1); p=trie[p][tmp^1]; }else{ ans=(ans<<1)+tmp; p=trie[p][tmp]; } } return ans; } void xor_max(){ memset(d,0,sizeof(d)); memset(trie,0,sizeof(trie)); memset(head,0,sizeof(head)); memset(nxt,0,sizeof(nxt)); memset(v,0,sizeof(v)); num=0; v[0]=1; tot=0; for(int i=0;i<n-1;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dfs(0); int ans=0; for(int i=0;i<n;i++){ insert(d[i]); if(i){ ans=max(ans,d[i]^search(d[i])); } } cout<<ans<<endl; } int main(){ while(cin>>n){ xor_max(); } return 0; }