The Xor-longest Path [WOJ2290] [0/1trie]

传送门

考虑维护每个点到根的异或和 , 发现一条路径两个点的异或和就是他们到根的异或和的异或

因为lca 到根的那一段自己与自己异或 , 就变成0了 , 接着就变成找两个异或最大的点 , 0/1trie 解决

#include<bits/stdc++.h>
#define N 100050
using namespace std;
int first[N],next[N*2],to[N*2],w[N*2],tot;
int dis[N],ch[N*32][2],val[N*32],n,m,ans,sign;
//void Init(){
//	memset(first,0,sizeof(first));
//	memset(next,0,sizeof(next));
//	memset(to,0,sizeof(to));
//	memset(w,0,sizeof(w)); tot = sign = ans = 0;
//	memset(dis,0,sizeof(dis));
//	memset(ch,0,sizeof(ch));
//	memset(val,0,sizeof(val));
//}
void add(int x,int y,int z){
	next[++tot]=first[x],first[x]=tot,to[tot]=y,w[tot]=z;
}
void dfs(int u,int f){
	for(int i=first[u];i;i=next[i]){
		int t=to[i]; if(t==f) continue;
		dis[t] = dis[u] ^ w[i]; dfs(t,u);
	}
}
void Insert(int x){
	int now = 0;
	for(int i=31;i>=0;i--){
		int pos = ((x>>i)&1);
		if(!ch[now][pos]) ch[now][pos]=++sign;
		now = ch[now][pos];
	} val[now] = x;
}
int Quary(int x){
	int now = 0;
	for(int i=31;i>=0;i--){
		int pos = ((x>>i)&1)==0;
		if(ch[now][pos]) now = ch[now][pos];
		else now = ch[now][pos^1]; 
	} return val[now];
}
int main(){
	scanf(\"%d%d\",&n,&m);
	for(int i=1;i<n;i++){
		int x,y,z; scanf(\"%d%d%d\",&x,&y,&z);
		add(x,y,z),add(y,x,z);
	} dfs(1,0);
	for(int i=1;i<=n;i++){
		ans = max(ans,dis[i]^Quary(dis[i])); 
		Insert(dis[i]^m);
	} printf(\"%d\",ans); return 0;
}