对于xor有一个非常重要的性质
A xor B xor B=A 并且满足交换律和结合律
这道题是求无根树上最长的xor路径
我们知道，无根树的题目我们都是要想办法转化为有根树来处理
当我们确定了一个根，根到每个节点i的xor路径f[i]可知
则在树中，任意两个节点ij间的xor路径长度即为f[i] xor f[j]
为什么，利用之前的性质我们可以知道
路径长度=d[i,LCA] xor d[LCA,j]=d[i,LCA] xor d[LCA,root] xor d[root,LCA] xor d[LCA,j]=f[i] xor f[j]
这样就转化为一个经典的问题，在一堆数中找两个数是xor值最大
这个我们可以将所有值得二进制建成一棵trie，
然后穷举每个数，遍历trie树找到和这个数xor值最大的数（贪心）
PS：这道题和poj3764一样，只不过bzoj1954标号是1~n，poj是0~n-1
但我改了标号始终在poj上WA……求指教
code（按bzoj1954）
type node=record
point,next,cost:longint;
end; var son:array[..,..] of longint;
p,f:array[..] of longint;
v:array[..] of boolean;
edge:array[..] of node;
ans,m,n,len,t,r,i,x,y,z:longint; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure add(x,y,z:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].cost:=z;
edge[len].next:=p[x];
p[x]:=len;
end; procedure build(x:longint);
var p,i,y:longint;
begin
p:=;
for i:= downto do
begin
y:=( shl i) and x;
if y<> then y:=;
if son[p,y]=- then
begin
inc(t);
son[p,y]:=t;
end;
p:=son[p,y];
end;
end; procedure dfs(x:longint);
var i,y:longint;
begin
i:=p[x];
v[x]:=true;
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
f[y]:=f[x] xor edge[i].cost;
dfs(y);
end;
i:=edge[i].next;
end;
end; function getans(x:longint):longint;
var y,p,s,i:longint;
begin
p:=;
s:=;
for i:= downto do
begin
y:=( shl i) and x;
if y<> then y:=;
if son[p,-y]<>- then
begin
s:=s+ shl i;
p:=son[p,-y];
end
else p:=son[p,y];
end;
exit(s);
end; begin
while not eof do
begin
readln(n);
fillchar(p,sizeof(p),);
len:=;
for i:= to n- do
begin
readln(x,y,z);
// inc(x);
// inc(y);
add(x,y,z);
add(y,x,z);
end;
fillchar(v,sizeof(v),false);
fillchar(son,sizeof(son),);
f[]:=;
t:=;
dfs();
for i:= to n do
build(f[i]); ans:=;
for i:= to n do
ans:=max(ans,getans(f[i]));
writeln(ans);
end;
end.