The xor-longest Path POJ - 3764
题意：
本题是求异或路径的最大。
思路：
关于求n个数里，异或最大的思路。传送门。先把每个点到根的异或路径算出来d【i】。那么u和v两两之间的异或路径。就可以转换成d【u】^d【v】。之后问题就转换成：n个数里，异或最大。
反思：
本题要用到快读。（不然会TLE。当然scanf也可。）
AC
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <algorithm>
#define fzhead EDGE(int _to, int _next, int _val)
#define fzbody to(_to), next(_next), val(_val)
#define mst(x,a) memset(x,a,sizeof(x))
#define For(i,x,y) for(int i=(x); i<=(y); i++)
using namespace std
;
inline int read(){
int ans
=0;
char r
=getchar();bool neg
=false;
while(r
<'0'||r
>'9'){if(r
=='-')neg
=true;r
=getchar();}
while(r
>='0'&&r
<='9'){ans
=ans
*10+r
-'0';r
=getchar();}
return (neg
)?-ans
:ans
;
}
void write(int x
){
if(x
<0){putchar('-');x
=-x
;}
if(x
>9)write(x
/10);
putchar(x
%10+'0');
}
typedef long long ll
;
const int maxnode
=4e6+10;
int ch
[maxnode
][2];
int sz
=2;
void clear(){sz
=2;mst(ch
[1],0);}
void insert(ll str
){
int u
=1;
for(int i
=32; i
>=0; i
--){
ll k
=(str
>>i
)&1;
if(!ch
[u
][k
]){
mst(ch
[sz
],0);
ch
[u
][k
]=sz
++;
}
u
=ch
[u
][k
];
}
return;
}
ll
find(ll str
){
ll res
=0,u
=1;
for(int i
=32; i
>=0; i
--){
ll k
=(str
>>i
)&1;
if(ch
[u
][k
^1]){
u
=ch
[u
][k
^1];
res
+= (1<<i
);
}else u
=ch
[u
][k
];
}
return res
;
}
const int maxn
=1e5+10;
const int maxm
=2e5+10;
struct EDGE
{
int to
,next
,val
;
EDGE(){}
fzhead
:fzbody
{}
}e
[maxm
];
int cnt
,head
[maxn
],n
;
int d
[maxn
];
void init(){
clear();
cnt
=0;
mst(head
,-1);
mst(d
,0);
}
void add(int bg
, int to
, int val
){
e
[cnt
]=EDGE(to
,head
[bg
],val
);
head
[bg
]=cnt
++;
}
void dfs(int u
, int fa
){
for(int i
=head
[u
]; i
!=-1; i
=e
[i
].next
){
int v
=e
[i
].to
;
if(v
==fa
)continue;
d
[v
]=d
[u
]^e
[i
].val
;
dfs(v
,u
);
}
}
int main()
{
while(cin
>>n
){
init();
int u
,v
,w
;
For(i
,1,n
-1){
u
=read();v
=read();w
=read();
add(u
,v
,w
);add(v
,u
,w
);
}
dfs(0,-1);
ll ans
=0;
for(int i
=0; i
<n
; i
++){
insert(d
[i
]);
ans
=max(ans
,find(d
[i
]));
}
cout
<<ans
<<endl
;
}
return 0;
}
