题解
求出从根出发到每一个点的异或距离，然后问题转化为在这些距离中找两个异或值最大的。
这是个经典问题，只需要在用trie树查询时进行反向行走即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
using namespace std;
typedef unsigned int ll;
struct Tree{
int l,r;
Tree(){l=r=-1;}
};
typedef struct{
int v,_next;
ll cost;
}Edge;
Edge edge[200005];
int cnt=0,at[100005];
void addedge(int _u,int _v,ll _cost){
edge[cnt].v=_v,
edge[cnt].cost=_cost,
edge[cnt]._next=at[_u],
at[_u]=cnt++;
}
int n,siz=1;
Tree tr[3000005];
ll vx[100005];
bool vis[100005];
void Trie_insert(ll num){
//printf("%u\n",num);
for(ll j=(1<<31),cur=0;j;j>>=1)
if((j&num)==0){//l:0 r:1
if(tr[cur].l<0)
tr[cur].l=siz++;
cur=tr[cur].l;
}else{
if(tr[cur].r<0)
tr[cur].r=siz++;
cur=tr[cur].r;
}
}
ll Trie_search(ll x){
ll res=0;
for(ll j=1<<31,cur=0;j;j>>=1){
if(x&j){
if(tr[cur].l>0)res+=j,cur=tr[cur].l;
else cur=tr[cur].r;
}else{
if(tr[cur].r>0)res+=j,cur=tr[cur].r;
else cur=tr[cur].l;
}
}
return res;
}
void dfs(int cur,ll val){
for(int i=at[cur];i!=-1;i=edge[i]._next){
int _v=edge[i].v;
if(!vis[_v])
vis[_v]=1,
vx[_v]=val^edge[i].cost,
Trie_insert(vx[_v]),
dfs(_v,vx[_v]);
}
}
int main(){
while(~scanf("%d",&n)){
for(int i=0;i<siz;i++)
tr[i].l=tr[i].r=-1;
siz=1,cnt=0;
memset(at,-1,sizeof(at));
memset(vis,0,sizeof(vis));
int u,v;ll c;
for(int i=0;i<n-1;i++)
scanf("%d%d%u",&u,&v,&c),
addedge(u,v,c),
addedge(v,u,c);
dfs(0,0);
vx[0]=0;
//Trie_insert(0u);
ll ans=0;
for(int i=0;i<n;i++)
ans=max(ans,Trie_search(vx[i]));
printf("%u\n",ans);
}
return 0;
}