P4551 最长异或路径

给定树上 \(n\) 个点和边权，求两点间所有边权的异或和最大。 \(n\leq 10^5\) 。

首先如果假定一个根，那么所有点到根的距离 \(dis[i]\) 中两两异或得到的就是答案。（ \(x,y\) 两点的距离= \(dis[x]\,\,xor\,\,dis[y]\) ,从lca到根的距离会因为异或2次而被消掉）。那么用 \(Trie\) 树来维护前面的 \(dis[i]\) ，在查询之后将其加入即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace Trie{
	int trie[60000000][2],tcnt=1;
	inline void insert(ll num){
		ll p=1;
		for(int i=30;i>=0;--i){
			if(trie[p][(num>>i)&1]){
				p=trie[p][(num>>i)&1];
			}
			else{
				trie[p][(num>>i)&1]=++tcnt;
				p=tcnt;
			}
		}
	}
	inline ll find(ll num){
		ll p=1,ret=0;
		for(int i=30;i>=0;--i){
			if(trie[p][((num>>i)&1)^1]){
				p=trie[p][((num>>i)&1)^1];
				ret+=1<<i;
			}
			else{
				p=trie[p][(num>>i)&1];
			}
		}
		return ret;
	}
}
using namespace Trie;

ll head[100005],ecnt=1,val[100005];
struct node{
	ll nxt,to,w;
}nd[1000005];

inline void adde(int u,int v,ll w){
	nd[++ecnt].nxt=head[u];
	nd[ecnt].to=v;
	nd[ecnt].w=w;
	head[u]=ecnt;
}
ll n,ans;

void dfs(int x,int fa){
	for(int i=head[x];i;i=nd[i].nxt){
		if(nd[i].to==fa)
			continue;
		val[nd[i].to]=val[x]^nd[i].w;
		dfs(nd[i].to,x);
	}
}


int main(){
	scanf("%lld",&n);
	for(int i=1;i<n;++i){
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		adde(u,v,w);
		adde(v,u,w);
	}
	dfs(1,1);
	for(int i=1;i<=n;++i){
		ans=max(ans,find(val[i]));
		insert(val[i]);
	}
	printf("%lld",ans);
	return 0;
}