Xor-MST 题解

题目描述

给定一个 $n$ 个点的完全无向图，每个点 $i$ 有一个权值 $a_i$，边 $(i,j)$ 的权值为 $a_i \oplus a_j$（$\oplus$ 表示按位异或）。求该图的最小生成树（MST）的权值和。

• $1 \le n \le 2\times 10^5$
• $0 \le a_i < 2^{30}$

算法分析

1. 异或的性质与 01-Trie

对于异或问题，通常使用 01-Trie（二进制字典树）来快速查询与给定数异或值最小的数。将每个数的二进制位从高位到低位插入 Trie，查询时尽量沿相同方向走，若没有则走另一方向并累加该位权值 $2^i$，时间复杂度 $O(\log C)$，其中 $C=2^{30}$。

2. 最小生成树与分治思想

本题不能直接使用 Kruskal 或 Prim，因为完全图的边数为 $O(n^2)$。利用异或的特殊性，可以采用 分治法：

• 将 $n$ 个数排序并去重（相同权值的点之间边权为 $0$，可直接合并）。
• 建立一棵包含所有数的 01-Trie，并在每个节点记录该子树所包含的数在排序后数组中的下标范围 $[L,R]$。
• 在 Trie 上递归处理：对于节点 k（对应二进制位 dep），如果它同时拥有左右孩子，则左右子树之间的点必须通过一条边连接。这条边的最小可能权值等于： $ \min_{x \in \text{left}} \min_{y \in \text{right}} (x \oplus y) $ 由于左右子树已经按位划分，它们在第 dep 位上的值不同，因此任何跨左右子树的异或值至少为 $2^{dep}$。而低位可以做到异或为 $0$（只要在子树内继续匹配）。所以最小异或值可以通过 枚举左子树中的所有数，在右子树的 Trie 中查询最小异或值得到，并加上 $2^{dep}$。
• 该节点的贡献 = 左子树内部 MST 权值 + 右子树内部 MST 权值 + 跨左右子树的最小边权。
• 递归基：当 dep == -1 或节点为空时，返回 $0$。

3. 正确性说明

• 在 Trie 中，每个内部节点对应一个二进制前缀。所有具有相同前缀的数构成一个连通块，而左右孩子分别对应前缀后接 0 或 1。
• 跨左右子树的最小边即为连接这两个“前缀块”的最小异或边，它必然属于某棵 MST（Borůvka 算法的思想）。
• 由于递归处理了所有节点，且每个节点处的计算都是取最小可能边，最终累加和即为 MST 的总权值。

4. 复杂度

• 建 Trie 及区间标记：$O(n \log C)$。
• 递归过程中，每个数在被枚举时只会出现在它所在节点的“轻儿子”中（即大小较小的子树）。每次查询需要 $O(\log C)$，总时间复杂度为 $O(n \log n \log C)$，在 $n \le 2\times 10^5$ 时可以通过。

代码实现

#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, a[maxn], L[maxn * 32], R[maxn * 32], ch[2][maxn * 32], rt, cnt;

// 插入数 a[id] 到 Trie 中，当前深度 dep
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;
    int bit = (a[id] >> dep) & 1;
    insert(ch[bit][k], id, dep - 1);
}

// 在节点 k 的子树中查询与 x 异或的最小值，当前深度 dep
int query(int k, int x, int dep) {
    if(dep == -1) return 0;
    int bit = (x >> dep) & 1;
    if(ch[bit][k]) return query(ch[bit][k], x, dep - 1);
    return query(ch[bit ^ 1][k], x, dep - 1) + (1 << dep);
}

// 递归计算以节点 k 为根的子树内部 MST 权值和
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);          // 排序去重
    n = unique(a + 1, a + n + 1) - (a + 1);
    rep(i, 1, n) insert(rt, i, 30);  // 插入 Trie，深度 30（因为 0 ≤ a_i < 2^30）
    printf("%lld\n", dfs(rt, 30));
    return 0;
}