poj3764 The xor-longest Path

poj3764 The xor-longest Path

---

原题链接vjudge
原题链接poj

---

题目大意：一棵树边有权值，求权值异或和最大的路径
想出了暴力，那就是对每个点求出从根到它所有边的异或和v[i]（dfs），然后路径a-b的权值异或和就是v[a] xor v[b] 因为LCA和LCA上面的都被异或掉了没有了QaQ
问题转化为选两个数的最大异或和
这个用trie树搞，先把所有数的二进制都存进trie树，然后枚举每个树在trie树上走，如果有和这一位不同的就走那一个，然后累加答案

---

Code

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#define Fname "xor"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define lb(o) ((o)&-(o))
typedef long long ll;
il int gi(){
    rg int x=0;rg char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
const int maxn=1e5+1,maxm=maxn<<1;
int n;
int fir[maxn],dis[maxm],nxt[maxm],w[maxm],id;
il vd add(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
int v[maxn];
il vd dfs(int x,int fa=-1){erep(i,x)if(dis[i]^fa)v[dis[i]]=v[x]^w[i],dfs(dis[i],x);}
int trie[32*maxn][2],tot=0;
il vd insert(int x){
    int now=0;bool s;
    drep(i,30,0){
	s=x&(1<<i);
	if(!trie[now][s])trie[now][s]=++tot;
	now=trie[now][s];
    }
}
il int find(int x){
    int now=0,res=0;bool s;
    drep(i,30,0){
	s=x&(1<<i);
	if(trie[now][s^1])now=trie[now][s^1],res|=1<<i;
	else now=trie[now][s];
    }return res;
}
int main(){
    freopen(Fname".in","r",stdin);
    freopen(Fname".out","w",stdout);
    while(scanf("%d",&n)==1){
	int a,b,c;
	rep(i,1,n)fir[i]=0;
	id=0;
	rep(i,2,n)a=gi()+1,b=gi()+1,c=gi(),add(a,b,c),add(b,a,c);
	v[1]=0,dfs(1,0);
	int ans=0;
	tot=0;
	rep(i,0,32*n)trie[i][0]=trie[i][1]=0;
	rep(i,1,n)insert(v[i]);
	rep(i,1,n)ans=max(ans,find(v[i]));
	printf("%d
",ans);
    }
    return 0;
}