传送门

题意说给一棵树，若在任意两点之间加边，权值为路径的异或和。

在保证图联通的情况下可以删边。

求如何操作使得最后这张图的边权和最小。

做法是先发现任意两点的边权其实可以看做给定，就是到根节点的异或和。

那么先预处理出来所有点的异或和当作点权，问题转化为：给定一些点，任意两点之间连边为其二的异或和，求最小生成树。

用到了Boruvka的思想，合并两个连接边权最小的连通块。

把所有点插入trie树上，考虑任意一层的任意一个点，最优的合并必然是要合并左右子树，因为更高位是相同的，异或得 0 。而合并所需要得代价就是其左子树所有点和右子树所有点的异或最小值。

分治来求每个节点的代价，左边的值都插入trie，枚举右边查询最小值。查完以后把trie清空。直接把所有idx的点标记为0即可。

#include<bits/stdc++.h>
using namespace std;
using namespace std;

const int N = 100010, M = 3000000;

int a[N], son[M][2], idx;

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

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int s = (x >> i) & 1;
        if (son[p][s])
            p = son[p][s];
        else res += 1 << i, p = son[p][!s];
    }
    return res;
}
int n; 
long long ans;
void dfs(int l, int r, int dep)
{
    if(dep == -1 || l >= r) return;
    int mid = l - 1;
    while(mid < r && ((a[mid + 1] >> dep) & 1) == 0) mid++;

    dfs(l, mid, dep - 1); dfs(mid + 1, r, dep - 1);
    if(mid == l - 1 || r == mid) return;
    for(int i = l; i <= mid; i++) insert(a[i]);

    int res = INT_MAX;
    for(int j = mid + 1; j <= r; j++)
    {
        res = min(res, search(a[j]));
    }
    ans += res;
    for(int j = 0; j <= idx; j++) son[j][0] = son[j][1] = 0;
    idx = 0;
}

int e[N << 1], pre[N << 1], h[N], val[N << 1], cnt;
void add(int u, int v, int w)
{
    e[cnt] = v; pre[cnt] = h[u]; val[cnt] = w; h[u] = cnt++;
}

int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 1; i < n; i++) 
    {
        int u, v, w; cin >> u >> v >> w;
        ++u, ++v;
        add(u, v, w); add(v, u, w);
    }
    function<void(int,int,int) > fun = [&](int x, int fa, int v) 
    {
        a[x] = v;
        for(int i = h[x]; ~i; i = pre[i])
        {
            int y = e[i];
            if(y == fa) continue;
            fun(y, x, v ^ val[i]);
        }
    };
    fun(1, - 1, 0);
    sort(a + 1, a + 1 + n);
    // for(int i = 1; i <= n; i++) cerr << a[i] << ' '; cerr << endl;
    // cerr << "yes" << endl;
    dfs(1, n, 29);
    cout << ans << endl;
}