XOR-MST

完全图边权为异或值;用 Borůvka + 可删除二进制 trie,每轮查询块外最小异或边,O(B n log n)。

来源 Codeforces 888 G · 难度 Codeforces 2400 · 标签 生成树 / Borůvka / Trie / 位运算

题目描述

给定 𝑛 个非负整数 𝑎𝑖。在完全图上定义边权

𝑤(𝑖,𝑗)=𝑎𝑖xor𝑎𝑗

求该图最小生成树的权值和。

1≤𝑛≤2×105,0≤𝑎𝑖<230。

题解

完全图有 𝑂(𝑛2) 条边,用 Borůvka 求 MST。每轮为每个连通块找一条最小出边。

把当前所有 𝑎𝑖 插入一棵 二进制 trie,节点记录子树内的数字个数。

对每个连通块 𝐶:

  1. 把 𝐶 中所有点从 trie 中删除;
  2. 对 𝐶 中每个点 𝑖,在 trie 中查询与 𝑎𝑖 异或最小的值;此时 trie 中只剩块外的点;
  3. 查询完把 𝐶 中所有点重新插入。

删除和插入都沿 trie 的一条根到叶路径,单次 𝑂(𝐵)。查询从高位到低位走:若与当前位相同的子树非空,就走同侧,否则走相反侧。这样当前位的异或结果为 0,因此得到块外最小异或值。

对 𝐶 内所有点的查询结果取最小者,就是 𝐶 的最小出边。

复杂度

每个点每轮删除、查询、插入各一次,每次 𝑂(𝐵),所以每轮 𝑂(𝐵𝑛)。Borůvka 最多 𝑂(log𝑛) 轮,总复杂度 𝑂(𝐵𝑛log𝑛),空间 𝑂(𝐵𝑛)。

参考

源码位置