luogu_4551【题解】最长异或路径 trie树

#include<cstdio>
#include<algorithm>
#define rr register
#define sc(x) scanf("%d",&x) 
using namespace std;
const int maxn=100001;
int n;
int head[maxn],tot;
struct node{
    int nxt,to,val;
    #define to(x) e[x].to
    #define val(x) e[x].val
    #define nxt(x) e[x].nxt
}e[maxn<<1];
inline void add(int u,int v,int w){
    to(++tot)=v,val(tot)=w;
    nxt(tot)=head[u];
    head[u]=tot;    
}
int xorr[maxn];
//所有点到根节点的异或值
inline void dfs(int now,int ls){
    for(rr int i=head[now];i;i=nxt(i)){
        if(to(i)!=ls){
            xorr[to(i)]=xorr[now]^val(i);
            dfs(to(i),now);
        }
    }
}
int cnt,trie[maxn*31][2];
inline void build(int x,int p){
    for(rr int i=1<<30;i;i>>=1){
        bool c=x&i;
        if(!trie[p][c])
            trie[p][c]=++cnt;
        p=trie[p][c];
    }
}
inline int ask(int x,int p){
    int ans=0;
    for(rr int i=1<<30;i;i>>=1){
        bool c=x&i;
        if(trie[p][c^1]) ans+=i,p=trie[p][c^1];
        else p=trie[p][c];
    }
    return ans;
}
int main()
{
    sc(n);
    for(rr int i=1;i<n;i++){
        int u,v,w;
        sc(u),sc(v),sc(w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
    int ans=0;
    for(rr int i=1;i<=n;i++) build(xorr[i],0);
    for(rr int i=1;i<=n;i++) ans=max(ans,ask(xorr[i],0));
    printf("%d\n",ans);
    // system("pause");
    return 0;
}