- #include<bits/stdc++.h>
- using namespace std;
- const int N=1e5+5;
- int n,head[N<<1],ch[3100005][2],tot,d[N];
- struct node{int to,next,val;}e[N<<1];
- void add(int u,int v,int val){e[++tot].to=v;e[tot].val=val;e[tot].next=head[u];head[u]=tot;}
- void dfs(int u,int fa){
- for(int i=head[u];i;i=e[i].next){
- int v=e[i].to;
- if(v!=fa)
- d[v]=d[u]^e[i].val,dfs(v,u);
- }
- }
- void bt(int k){
- int u=1;
- for(int i=31;i>=0;i--){
- bool x=k&(1<<i);
- if(!ch[u][x])ch[u][x]=++tot;
- u=ch[u][x];
- }
- }
- int qr(int k){
- int u=1,ans=0;
- for(int i=31;i>=0;i--){
- bool x=k&(1<<i);
- if(ch[u][x^1])ans+=(1<<i),u=ch[u][x^1];
- else u=ch[u][x];
- }
- return ans;
- }
- int main(){
- scanf("%d",&n);
- for(int i=1,u,v,w;i<n;i++){
- scanf("%d%d%d",&u,&v,&w);
- add(u,v,w);add(v,u,w);
- }
- dfs(1,0);
- int ans=0;
- for(int i=1;i<=n;i++)bt(d[i]);
- for(int i=1;i<=n;i++)ans=max(ans,qr(d[i]));
- cout<<ans<<endl;
- }
模板题, 进行异或操作后会抵消, 相当于是找两个数进行异或
来源: http://www.bubuko.com/infodetail-3161100.html