XOR-MST
完全图边权为异或值;用 Borůvka + 可删除二进制 trie,每轮查询块外最小异或边,O(B n log n)。来源 Codeforces 888 G · 难度 Codeforces 2400 · 标签 生成树 / Borůvka / Trie / 位运算
题目描述
给定 个非负整数 。在完全图上定义边权
求该图最小生成树的权值和。
,。
题解
完全图有 条边,用 Borůvka 求 MST。每轮为每个连通块找一条最小出边。
把当前所有 插入一棵 二进制 trie,节点记录子树内的数字个数。
对每个连通块 :
- 把 中所有点从 trie 中删除;
- 对 中每个点 ,在 trie 中查询与 异或最小的值;此时 trie 中只剩块外的点;
- 查询完把 中所有点重新插入。
删除和插入都沿 trie 的一条根到叶路径,单次 。查询从高位到低位走:若与当前位相同的子树非空,就走同侧,否则走相反侧。这样当前位的异或结果为 ,因此得到块外最小异或值。
对 内所有点的查询结果取最小者,就是 的最小出边。
复杂度
每个点每轮删除、查询、插入各一次,每次 ,所以每轮 。Borůvka 最多 轮,总复杂度 ,空间 。
参考
- 题目链接:CF 888G XOR-MST。