The xor-longest Path
题目描述
给定一棵(n≤100 000)个点的带权树，求树上最长的异或和路径。
输入
多组数据。每组数据第一行一个整数n((1≤n≤100 00)，接下去n-1行每行三个整数(u(0≤u<n) ,v(0≤v<n) ,w(0≤w<2^{31})),表示u和v之间的长度为w的边。
输出
对于每组数据输出结果。
样例输入
4
1 2 3
2 3 4
2 4 6
样例输出
7
题解
其实也是很简单的一道题,因为题目输入是一棵树,有边权,要我们求树上的最长异或和路径,可以想到这样一个性质,一遍深搜处理出每个点到根节点的异或值d[x],那么树上任意两个点的异或和其实就是d[x]^d[y],如果实在不懂可以自己动手画一棵树感受一下,那么问题就转化成了在d[1]~d[n]中任选两个点,求异或值最大,也就是这道题The Xor Largest Pair,剩下的也不用讲了,trie树裸题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define in(i) (i=read())
using namespace std;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') {ans=(ans<<1)+(ans<<3)+i-'0'; i=getchar();}
return ans*f;
}
int tot,n,cnt,ans;
struct edge {
int to,next,v;
}e[200010];
int head[100010];
int trie[4000010][2],d[100010];
void add(int a,int b,int c) {
e[++cnt].to=b;
e[cnt].v=c;
e[cnt].next=head[a];
head[a]=cnt;
}
void dfs(int u,int fa) {
for(int i=head[u];i;i=e[i].next) {
int to=e[i].to;
if(to!=fa) {
d[to]=(d[u]^e[i].v);
dfs(to,u);
}
}
}
void insert(int x) {
int p=0;
for(int i=31;i>=0;--i) {
int c=(x>>i&1);
if(!trie[p][c]) trie[p][c]=++tot;
p=trie[p][c];
}
}
int find(int x) {
int sum=0,p=0;
for(int i=31;i>=0;--i) {
int c=(x>>i&1),o=(c^1);
if(trie[p][o]) p=trie[p][o],sum=(sum<<1|1);
else p=trie[p][c],sum<<=1;
}
return sum;
}
int main()
{
while(scanf("%d",&n)!=EOF) {
ans=tot=cnt=0;
memset(d,0,sizeof(d));
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
for(int i=1;i<n;++i) {
int u,v,c;
in(u); in(v); in(c);
add(u,v,c); add(v,u,c);
} dfs(1,0);
for(int i=1;i<=n;++i) {
ans=Max(ans,find(d[i]));
insert(d[i]);
}
printf("%d
",ans);
}
return 0;
}