P4551 最长异或路径（树上前缀异或01-trie）

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e5+10, M = 3e6+10;
vector<PII> e[N];
int idx;
//D[i]存的是i到根节点的边权异或和，两点的路径异或等于D的异或
int D[N],ne[M][2];
void add(int u,int v,int w)
{
	e[u].push_back({v,w});
}
void dfs(int u,int f)
{
	for(auto [v,w]:e[u])
	{
		if(v==f) continue;
		D[v] = (w^D[u]);
		dfs(v,u);
	}
}
//注意01trie的i的范围是受a[i]值域的影响而非个数
void insert(int t)
{
	int p = 0;
	for(int i=30;i>=0;--i)
	{
		int x = t>>i&1;
		if(!ne[p][x]) ne[p][x] = ++idx, p = idx;
		else p = ne[p][x];
	}
}
int query(int t)
{
	int p = 0;
	int res = 0;
	for(int i=30;i>=0;--i)
	{
		int x = t>>i&1;
		if(ne[p][x^1]) res += 1<<i, p = ne[p][x^1];
		else p = ne[p][x];
	}
	return res;
}
void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<n;++i)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,0);
	int maxn = 0;
	insert(0);
	//注意i点到根节点的路径也是一组可能的合法解
	for(int i=2;i<=n;++i)
	{
		//cout<<D[i]<<'\n';
		maxn = max(maxn,query(D[i]));
		insert(D[i]);
	}
	cout<<maxn<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}