G. Xor-MST

使用 \(01-Trie\) 树求解.

解法1

观察到我们合并两个点 \(x\) \(y\) 的代价是和 \(lca(x, y)\) 的深度有关的, 深度越深, 代价越少.

具有相同前缀的点一定是先合并成一个连通块的, 这样我们就可以直接在 \(Trie\) 树上 \(dfs\) 求解.

class trie_01 {
    static const int size = 1e5 * 30 + 10;  // 位数 * 数量
    static const int e = 2;                 // 01
    static const int n = 30;                // max = 2 ^ n - 1;
    int idx;
    std::array<std::array<int, e>, size> tr;
    std::array<int, size> cnt;

    int newnode() {
        tr[idx].fill(0);
        cnt[idx] = 0;
        idx++;
        return idx - 1;
    }

    static int to_int(int a, int d) {
        return (a >> d) & 1;
    }

public:
    LL ans;
    trie_01() : idx(0), ans(0) { newnode(); }
    void insert(int s) {
        int p = 0;
        for (int i = n - 1; i >= 0; i--) {
            int x = to_int(s, i);  // 要映射到0开始的喵
            if (!tr[p][x]) {
                tr[p][x] = newnode();
            }
            p = tr[p][x];
            cnt[p]++;
        }
    }
    void clean() {
        idx = 0;
        ans = 0;
        newnode();
    }

    int query_xor_min(int mask, int p = 0, int d = n - 1) {
        int res = 0;
        for (int i = d; i >= 0; i--) {
            int x = to_int(mask, i);
            if (tr[p][x])
                p = tr[p][x];
            else
                p = tr[p][!x], res += 1 << i;
        }
        return res;
    }

    void dfs(int p, int d, int mask, int pr, int dd, int &res) {
        if (d == 0) {
            res = min(res, query_xor_min(mask, pr, dd));
            return;
        }
        if (tr[p][0])
            dfs(tr[p][0], d - 1, mask, pr, dd, res);
        mask += 1 << (d - 1);
        if (tr[p][1])
            dfs(tr[p][1], d - 1, mask, pr, dd, res);
    }

    int find(int pl, int pr, int d) {
        int res = INF;
        if (cnt[pr] < cnt[pl])
            swap(pr, pl);
        dfs(pl, d, 0, pr, d - 1, res);
        return res;
    }

    void solve(int d, int p) {
        if (d == 0)
            return;
        if (tr[p][0])
            solve(d - 1, tr[p][0]);
        if (tr[p][1])
            solve(d - 1, tr[p][1]);
        if (tr[p][0] && tr[p][1])
            ans += (1 << (d - 1)) + find(tr[p][0], tr[p][1], d - 1);
    }
} tr;

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        tr.insert(a);
    }
    tr.solve(30, 0);
    cout << tr.ans << '\n';
}

解法2

直接使用 \(Boruvka\’s\ algorithm\).

即每次迭代, 对于每个连通块, 找到连通块向外连的代价最小的边, 这样找到了 \(n\) 个边, 易得至少有 \(n / 2\) 个不同的边, 连上后连通块数量至少减半, 故只要 \(O(log)\) 次迭代.

每次找联通块向外连的最小代价的边, 先把连通块中的点都移除 \(Trie\), 然后找, 最后再重新插入, 这样每次迭代的复杂度为 \(O(nlog(n))\).

总体复杂度为 \(O(nlog^2(n))\) , 但是猪咪 \(xkm\) 不知道为啥总是挂在第 13 个点 \(tle\), 调不出来了哎哎.