双倍经验：P4551 最长异或路径

#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<int, int>> e[112345];
int xorSum[112345];
void dfs(int u, int fa)
{
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].first;
        int w = e[u][i].second;
        if (v == fa)
            continue;
        xorSum[v] = xorSum[u] ^ w;
        dfs(v, u);
    }
}
// 0/1 trie
int tot, rt;
int l[112345 * 30], r[112345 * 30]; // 0/1 子节点
int cnt[112345 * 30];               //是否存在数
void init()
{
    memset(l, -1, sizeof(l));
    memset(r, -1, sizeof(r));
    memset(cnt, 0, sizeof(cnt));
    tot = 1;
    rt = 1;
}
void insert(int x)
{
    int now = rt;
    for (int i = 30; i >= 0; i--)
    {
        if (x & (1 << i))
        {
            if (r[now] == -1)
                r[now] = ++tot;
            now = r[now];
        }
        else
        {
            if (l[now] == -1)
                l[now] = ++tot;
            now = l[now];
        }
    }
    cnt[now]++;
}
int query(int x)
{
    int now = rt;
    int res = 0;
    // cout << x << " ========\n";
    for (int i = 30; i >= 0; i--)
    {
        if (x & (1 << i))
        {
            if (l[now] != -1)
            {
                now = l[now];
                res = res | (1 << i);
                // cout << 1;
            }
            else
            {
                now = r[now];
                // cout << 0;
            }
        }
        else
        {
            if (r[now] != -1)
            {
                now = r[now];
                res = res | (1 << i);
                // cout << 1;
            }
            else
            {
                now = l[now];
                // cout << 0;
            }
        }
    }
    // cout << "\n";
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back(make_pair(v, w));
        e[v].push_back(make_pair(u, w));
    }
    xorSum[1] = 0;
    dfs(1, 0);
    /*
    for (int i = 1; i <= n; i++)
        cout << xorSum[i] << " ";
    cout << "\n";
    */
    init();
    insert(xorSum[1]);
    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        ans = max(ans, query(xorSum[i]));
        insert(xorSum[i]);
    }
    cout << ans << "\n";
    return 0;
}