AcWing 144. 最长异或值路径(vector存图,封装01Tire)
原题链接
中等
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >G[100005];
int val[100005];
struct Tire{
int tr[3000005][5],cnt,d[1000005];
void insert(int x)
{
int u=0;
for(int i=31;i>=0;i--)
{
int c=(x>>i)&1;
if(tr[u][c]==0) tr[u][c]=++cnt;
u=tr[u][c];
}
}
int find(int x)
{
int u=0,res=0;
for(int i=31;i>=0;i--)
{
int c=(x>>i)&1;
if(tr[u][!c])
{
res=(res<<1)+1;
u=tr[u][!c];
}
else
{
res=(res<<1);
u=tr[u][c];
}
}
return res;
}
}T;
void dfs(int x,int fa)
{
for(auto i:G[x])
{
if(i.second==fa) continue;
val[i.second]=i.first^val[x];
dfs(i.second,x);
}
}
int main()
{
int n;
cin>>n;
int nn=n-1;
while(nn--)
{
int u,v,w;
cin>>u>>v>>w;
G[u].emplace_back(w,v);
G[v].emplace_back(w,u);
}
dfs(0,-1);
for(int i=0;i<n;i++) T.insert(val[i]);
int ans=0;
for(int i=0;i<n;i++) ans=max(ans,T.find(val[i]));
cout<<ans;
}