题目描述

传送门

样例

Input:
4
0 1 3
1 2 4
1 3 6

Output:
7

算法

(Trie)

这个题目的基础版本是最大异或和这个题，做法是沿着Trie树的根节点往下走，贪心地找不同数位的点。
这个题其实就是套了一个树上差分的幌子，但是也是很好做的。
先来证明一个结论：将无根树强行拽成有根树(根节点为1号点)，记$d(i)$表示i号节点到1号节点路径的异或值。我们说，x号节点到y号节点的路径异或值为$d(x)$^$d(y)$。
证明：令$f(x,y)$为x节点到y节点的路径异或值。假设x与y的最近公共祖先为lca。则有：
$d(i)$^$d(j)$=$f(x,lca)$^$d(lca)$^$f(y,lca)$^$d(lca)$=$f(x,lca)$^$f(y,lca)$=$f(x,y)$。
证毕。

因此求出$d(i)$以后，再套最大异或和的板子就可以AC了，下面是AC代码。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
using namespace std;

int n;
int h[maxn], e[maxn * 2], ne[maxn * 2], w[maxn * 2], idx;
int d[maxn];
int tr[maxn * 35][2], cnt;

void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ; }

void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;

        d[j] = d[u] ^ w[i];
        dfs(j, u);
    }
}

void insert(int n)
{
    int p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int c = n >> i & 1;
        if (!tr[p][c]) tr[p][c] = ++cnt;
        p = tr[p][c];
    }
}

int query(int n)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int c = n >> i & 1;
        if (tr[p][c ^ 1])
        {
            p = tr[p][c ^ 1];
            res += (1 << i);
        }
        else p = tr[p][c];
    }

    return res;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ )
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }

    dfs(0, -1);

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        insert(d[i]);
        res = max(res, query(d[i]));
    }

    printf("%d\n", res);

    return 0;
}