https://www.luogu.com.cn/problem/P4551

这题思路本身并不难， LCA + 01trie （可以说是我见过最善良的紫题），因为 $XOR$ 运算具有自反律，因此只需要预处理每个节点到根节点路上的前缀xor，再结合树上 LCA 的特性，就可以把问题转化为最大异或对问题 (https://www.acwing.com/activity/content/problem/content/884/)

其坑点在于，dfs预处理时，不能想当然地在回溯时计算前缀xor，因为在回溯时计算，父节点的前缀xor在此时并没有算过，相当于误用0去与当前节点求前缀xor值，导致结果错误。

总结：要注意细节，不能想当然地去写一些没经过推敲的代码，尤其是在oi赛制的比赛中。

#include <iostream>

using namespace std;

const int N = 1000010;

int prefix_xor[N];
int trie_01[6 * N][2], idx = 0;

struct edge
{
    int to, val, next;
}e[N * 2];
int head[N], tot = 0;

void add_edge(int from, int to, int val)
{
    e[++tot].to = to;
    e[tot].val = val;
    e[tot].next = head[from];
    head[from] = tot;
}

void dfs(int u, int from)
{
    for (int i = head[u]; i; i = e[i].next)
    {
        int j = e[i].to;
        if (j == from) continue;

        prefix_xor[j] = prefix_xor[u] ^ e[i].val;
        dfs(j, u);
    }
}

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i--)
    {
        int &u = trie_01[p][x >> i & 1];
        if (!u) u = ++idx;
        p = u;
    }
}

int query(int x)
{
    int p = 0, res = 0;

    for (int i = 30; i >= 0; i--)
    {
        int s = x >> i & 1;
        if (trie_01[p][s ^ 1])
        {
            res += 1 << i;
            p = trie_01[p][s ^ 1];
        }
        else p = trie_01[p][s];
    }

    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i < n; i++)
    {
        int a, b, v;
        cin >> a >> b >> v;
        add_edge(a, b, v), add_edge(b, a, v);
    }

    dfs(1, 0);

    for (int i = 1; i <= n; i++) insert(prefix_xor[i]);

    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, query(prefix_xor[i]));

    cout << res << '\n';
}