P4551 最长异或路径

点击查看代码

#include<bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;
const int N=1e5+10;
int tr[N*31][2],idx;
int d[N];
vector<PII> adj[N];
int n;void dfs(int u,int fa,int sum)
{d[u]=sum;for(auto& edge : adj[u]){int v=edge.first;int w=edge.second;if(v!=fa){dfs(v,u,sum^w);}}
}void insert(int x)
{int p=0;for(int i=30;i>=0;i--){int bit=(x>>i)&1;if(!tr[p][bit]) tr[p][bit]=++idx;p=tr[p][bit];}
}int query(int x)
{int p=0,res=0;for(int i=30;i>=0;i--){int bit=(x>>i)&1;if(tr[p][1-bit]){p=tr[p][1-bit];res|=(1<<i);}else{p=tr[p][bit];} }return res;
}int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1;i<=n-1;i++){int u,v,w;cin>>u>>v>>w;adj[u].push_back({v,w});adj[v].push_back({u,w});}dfs(1,0,0);for(int i=1;i<=n;i++ ){insert(d[i]);}int max_ans=0;for(int i=1;i<=n;i++){max_ans=max(max_ans,query(d[i]));}cout<<max_ans<<"\n";return 0;
}