【题解】The XOR-longest Path

前置知识：01trie树
分析：

• 01trie树提供给我们的功能为我们塞进去一些数，然后我们可以logn内查询与其最大的异或和值。
• 那不刚好可以满足我们o（n^2）暴力吗。。

#include<bits/stdc++.h>
typedef long double ld;
#define INF (1ll<<60)-1
const int M=1e6+6;
#define MP make_pair
#define pb push_back
using namespace std;
const int N=1e5+5;
int num[M],cnt=1;
int d[M][2];
int tot,ans;
vector< pair<int,int> >g[N];
void update(int x){
    int p=1;
    for(int i=31;i>=0;i--){
        if(d[p][(x>>i)&1]==0) d[p][(x>>i)&1]=++cnt;
        p=d[p][(x>>i)&1];
        num[p]++;
    }
}

int query(int x){
    int res=0;
    int p=1;
    for(int i=31;i>=0;i--){
        int t=(x>>i)&1;
        if(num[d[p][1^t]]) p=d[p][1^t],res+=(1<<i);
        else p=d[p][t];
    }
    return res;
}
void dfs(int u,int fa,int dis){
    update(dis);
    for(auto it:g[u]){
        int v=it.first,w=it.second;
        if(v!=fa)
            dfs(v,u,dis^w);
    }
}
void dfs2(int u,int fa,int dis){
    ans=max(ans,max(query(dis),dis));
    for(auto it:g[u]){
        int v=it.first,w=it.second;
        if(v!=fa)
            dfs2(v,u,dis^w);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int u,v,w,i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        g[u].pb(MP(v,w));
        g[v].pb(MP(u,w));
    }
    dfs(1,0,0);
    dfs2(1,0,0);

    printf("%d\n",ans);
    return 0;
}