The XOR-longest Path(最长异或路径)

由题意可知这是一道经典的字典树模板
将数的二进制表示看做一个字符串，就可以建出字符集为{0,1}的 trie 树。

思路：

1.邻接表建树（链式前向星也行）
2.先dfs求出每个点到root的异或值，记为a[i],则有u到v的异或值等于a[u]^a[v]
3.u到root的路径与v到root的路径会有重叠的部分。因为自身异或自身等于0，所以题目可以转化为找一对(u,v),使a[u]^a[v]最大
4.套用字典树模板

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

struct node{
    int ne,w;
};

int ans,a[N];
vector<node> g[N];
struct Trie {
    int nex[N*32][2],cnt=0;

    void insert(int x) {  
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if (!nex[p][c]) nex[p][c] = ++cnt;  
            p = nex[p][c];
        }
    }
    int find(int x) { 
        int p = 0,res = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if(nex[p][c^1]) p=nex[p][c^1],res|=(1<<i);
            else p=nex[p][c];
        }
        return res;
    }
} t;

void dfs(int u,int fa){
    for(auto x:g[u]){
        int v=x.ne;
        if(v==fa) continue;
        a[v]=a[u]^x.w;
        dfs(v,u);
    }
}

void solve(){
    int n;cin>>n;
    _for(i,n){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    dfs(1,0);
    rep(i,1,n){
        t.insert(a[i]);
        ans=max(ans,t.find(a[i]));
    }
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
//     int t;cin>>t;while(t--)
    solve();
    return 0;
}