最长异或路径

#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;
}

模板题，进行异或操作后会抵消，相当于是找两个数进行异或