Xor-MST

题意： 给定个点，每个点的权值为，点和点之间的边的边权为。求由这个点构成的完全图的最小生成树的权值。
数据范围：

题解： 考虑分治法求解最小生成树的思想。那么可以将最小生成树的权值按照每一个二进制位进行分组，然后组内求解，再枚举比较两个组之间的数可以构成的最小权值即可，这里可以用树进行操作降低复杂度至。
具体做法：从最高位开始分组，先处理组与组之间的合并大小，然后再处理各自组内的生成树权值即可。

代码：

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

typedef long long ll;
const int N = 2e5 + 10;
int son[N * 32][2], idx = 1;
int n;
vector<int> tmp[N * 32];
ll ans = 0;

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

ll get(int p, int x, int dep) {
    if(dep < 0) return 0ll;
    int u = x >> dep & 1;
    if(son[p][u]) return get(son[p][u], x, dep - 1);
    return get(son[p][!u], x, dep - 1) + (1 << dep); 
}

void solve(int p, int dep) {
    int a = son[p][0], b = son[p][1];
    if(a && b) {
        ll mn = 1e18;
        if(tmp[a].size() > tmp[b].size()) swap(a, b);
        for(int i = 0; i < tmp[a].size(); ++i) mn = min(mn, get(b, tmp[a][i], dep - 1));
        ans += mn + (1 << dep);
    }

    if(a) solve(a, dep - 1);
    if(b) solve(b, dep - 1);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);
        insert(x);
    }

    solve(1, 30);
    printf("%lld\n", ans);

    return 0;
}