题解 CF888G 【Xor-MST】

· · 题解

妙妙题……

看到MST，想到Kruskal，看到异或，想到Trie

首先我们模拟一下Kruskal的流程：找到最小边，如果联通就忽略，未联通就加边

我们把所有点权值加入0-1\ Trie中，然后画张图，可以发现有n-1个点是有两个儿子的，而其他点都是只有0/1个儿子

权值最小的边应该是Trie中，LCA深度最大的两个数

而且这n-1个节点是一些在Trie中结尾节点的LCA

所以我们只需要遍历整颗Trie，然后对所有可能为LCA的点，找到一条最小的边，把它的两颗子树合并起来即可

一个小trick:我们可以把所有元素排好序，因为Trie上的点从左往右看是递增的，于是Trie的每一个节点就会对应排好序的数列中的一段区间，这样就不需要启发式合并之类的复杂操作了

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (1 << 30)
#define rep(i, s, t) for(int i = s; i <= t; ++ i)
#define maxn 200005
int n, m, a[maxn], L[maxn * 32], R[maxn * 32], ch[2][maxn * 32], rt, cnt;
void insert(int&k, int id, int dep) {
    if(!k) k = ++ cnt;
    if(!L[k]) L[k] = id; R[k] = id;
    if(dep == -1) return;
    insert(ch[(a[id] >> dep) & 1][k], id, dep - 1);
}
int query(int k, int x, int dep) {
    if(dep == -1) return 0;
    int v = (x >> dep) & 1;
    if(ch[v][k]) return query(ch[v][k], x, dep - 1);
    return query(ch[v ^ 1][k], x, dep - 1) + (1 << dep);
}
int dfs(int k, int dep) {
    if(dep == -1) return 0;
    if(ch[0][k] && ch[1][k]) {
        int ans = inf;
        rep(i, L[ch[0][k]], R[ch[0][k]]) {
            ans = min(ans, query(ch[1][k], a[i], dep - 1) + (1 << dep));
        }
        return dfs(ch[0][k], dep - 1) + dfs(ch[1][k], dep - 1) + ans;
    }
    else if(ch[0][k]) return dfs(ch[0][k], dep - 1);
    else if(ch[1][k]) return dfs(ch[1][k], dep - 1);
    return 0;
}
signed main() {
    scanf("%lld", &n);
    rep(i, 1, n) scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    rep(i, 1, n) insert(rt, i, 30);
    printf("%lld", dfs(rt, 30));
    return 0;
}