题面

Code

#include<bits/stdc++.h>
#define rgt register
#define N 100003
using namespace std;
struct Edge{
    int to,nxt,cost;
    Edge(int a,int b,int c):to(a),nxt(b),cost(c){}
    Edge(){}
}b[N<<1];
int head[N],f[N],bit[33];
int n,ans,t,T[N*33][2];
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void add(rgt int x,rgt int y,rgt int cost) {
    b[++t]=Edge(y,head[x],cost),head[x]=t;
    b[++t]=Edge(x,head[y],cost),head[y]=t;
}
inline void built(rgt int k,rgt int fa) {
    for(rgt int i=head[k],to;i;i=b[i].nxt) {
        to=b[i].to;
        if(to==fa) continue;
        f[to]=f[k]^b[i].cost,built(to,k);
    }
}
inline void Search(int k) {
    int i,c,p=1,res=0;
    for(i=30;i>=0;i--) {
        c=(k&bit[i])?0:1;
        if(T[p][c]) res+=bit[i],p=T[p][c];
        else p=T[p][c^1];
    }
    ans=max(ans,res);
}
inline void Insert(int k) {
    int i,c,p=1;
    for(i=30;i>=0;i--) {
        c=(k&bit[i])?1:0;
        if(!T[p][c])
            T[p][c]=++t;
        p=T[p][c];
    }
}
int main()
{
    int i,x,y,cost;
    n=read();
    bit[0]=1;for(i=1;i<31;i++) bit[i]=bit[i-1]<<1;
    for(i=1;i<n;i++)
        x=read(),y=read(),cost=read(),add(x,y,cost);
    built(1,0),t=1;
    for(i=2;i<=n;i++)
        ans=max(ans,f[i]),Search(f[i]),Insert(f[i]);
    printf("%d\n",ans);
    return 0;
}

devil.