03-Kruskal重构树与XORMST.md 7.5 KB
类生成树：Kruskal 重构树与 XOR-MST
本节目标
学完后，你应能把并查集合并历史显式建成 Kruskal 重构树，用 LCA 回答“两点何时连通”，并利用 XOR 权值的最高不同位递归削减完全图。
前置知识与课前自测
前置：Kruskal、并查集、LCA、二进制 Trie、分治。
- 按边权递增加入边时，两点第一次连通的阈值与 MST 路径有什么关系？
- 两个数最高不同位为 $b$ 时，它们 XOR 的第 $b$ 位是多少？低位最多能否抵消它？
- 完全图 XOR-MST 中，相同数对应的多个顶点是否影响总权？
自测答案
1. 等于某棵 MST 上两点路径的最大边权，也是 Kruskal 合并它们所在分量的时刻。 2. 第 $b$ 位为 1，低位之和小于 $2^b$，不能抵消。 3. 相同数之间边权为 0，可先用零权边连成一块，去重不改变答案。问题动机与核心知识
Kruskal 普通实现只保留最终 DSU，丢掉“什么时候合并”。重构树在每次成功合并两个分量时新建父节点，节点权为当前边权/时间，两个旧根作为孩子。原点是叶子，内部点权沿根方向不降。
两个原点的 LCA 正是首次把它们并入同一分量的合并节点。因此：
$$ \operatorname{value}(\operatorname{LCA}(u,v)) =\min{k:\ u,v\text{ 在前 }k\text{ 条边中连通}}. $$
XOR-MST 则使用最高位分层。若一组数在位 $b$ 同时含 0/1，任意连接两组的边都至少花 $2^b$；生成树必须至少选一条跨边，而组内可独立递归。只需求两组间最小 XOR，而不是显式生成所有跨边。
实现指南
- 重构树最多有 $2n-1$ 个节点，数组按
2*n开。 - 合并新节点后，要让两个旧 DSU 根的父亲指向新节点；新节点自身是新根。
- XOR 分治前排序去重；每层范围共享更高位前缀，当前位的 0/1 在排序中连续。
- Trie 查询只需处理当前位以下，跨组的当前位代价固定为 $2^b$。
精选例题 1：Qpwoeirut and Vertices
来源信息与题意
- VJudge：CodeForces-1706E Qpwoeirut and Vertices
- 原题：Codeforces Round 809 (Div. 2)
- 难度：2300；考点：按时间重构树、相邻点连通阈值、区间最大值
多组连通简单无向图，边按输入编号 $1..m$。每个询问 $[l,r]$ 求最小 $k$，使编号在该区间内的所有顶点使用前 $k$ 条边两两连通。总 $n\le10^5$，总 $m,q\le2\times10^5$。
Hint 1
按边编号做 Kruskal 式合并，新节点权值为边编号。Hint 2
两点 $u,v$ 的最早连通编号是重构树 LCA 权值。Hint 3
区间所有点连通，当且仅当每对相邻编号点 $(i,i+1)$ 都连通。Hint 4
预处理 `need[i]=value(LCA(i,i+1))`，答案是 `need[l..r-1]` 最大值。Observations、Editorial 与证明
边按编号递增处理，每次连接两个不同分量就新建合并节点。对阈值 $k$，区间相邻点全部连通则由传递性整个区间连通；整个区间连通也必然包含每对相邻点。因此最小共同阈值是相邻阈值最大值。
建树与 LCA 预处理 $O((n+m)\alpha(n)+n\log n)$，区间最大值用迭代线段树，每问 $O(\log n)$。
核心伪代码与参考实现附件
process input edges by index; every successful DSU merge creates a new parent node
new node value = current edge index; its children are the two old component roots
preprocess LCA on the reconstruction tree
need[i] = value(LCA(original_vertex_i, original_vertex_i+1))
answer(l,r) = max(need[l .. r-1]), or 0 when l == r
完整 GNU C++17 参考实现见附件：CodeForces-1706E.cpp
复盘与变式
若询问顶点集合不是编号连续区间，相邻编号链不再覆盖集合；可按 DFS 序、虚树或直接取集合在重构树上的最小公共祖先，取决于查询形式。
精选例题 2：Xor-MST
来源信息与题意
- VJudge：CodeForces-888G Xor-MST
- 原题：Educational Codeforces Round 32
- 大致难度：2300 左右；考点：XOR 最高位分治、二进制 Trie、隐式完全图
完全图有 $n\le2\times10^5$ 个点，点 $i$ 带值 $a_i<2^{30}$，边权为 $a_i\oplus a_j$。求 MST 权值。
Hint 1
相同值先用零权边连接，可去重。Hint 2
按最高位 $b$ 把当前组分成 0/1 两组；组内 MST 独立递归。Hint 3
若两组都非空，生成树必须且只需再选一条最便宜跨边。Hint 4
把较小一组的低位插入 Trie，查询另一组的最小低位 XOR；跨边还固定贡献 $2^b$。Observations、Editorial 与证明
当前范围内所有数共享更高位。按位 $b$ 分开后，任意跨边权均大于任一只由更低位构成的数；MST 可先在两侧各自连通，再用一条最小跨边连接。多用跨边会形成环，删除其中一条不更差。
递归处理两侧，跨边低位最小 XOR 用 Trie 求。排序与 30 层分治，当前实现复杂度 $O(n\log^2 A)$、空间 $O(n\log A)$ 的峰值；$\log A\le30$。
核心伪代码与参考实现附件
sort and deduplicate values
solve(group, bit):
split group by current bit
answer = solve(zero_side, bit-1) + solve(one_side, bit-1)
if both sides exist:
build a lower-bit binary trie for the smaller side
answer += 2^bit + minimum lower-bit XOR across the split
return answer
完整 GNU C++17 参考实现见附件：CodeForces-888G.cpp
复盘与变式
本题不是“所有完全图都能 Trie”。可分治是因为最高不同位严格支配全部低位；若边权改成按位 AND 或普通差值，递归结构和跨边性质都要重证。
灵活性训练：Envy
CodeForces-891C Envy 要判断每个询问给定的边集能否同时出现在某棵 MST。提示方向：按权值处理询问边，在全局 DSU 只合并更轻边；同一询问、同一权组用临时可回滚 DSU 检查是否成环。它把本章“同权批次不能提前合并”的原则提升到离线多询问，不作为后续硬前置。
扩展与联系
- Kruskal 重构树也可按边权建，用于路径瓶颈、阈值连通与离线询问。
- 最大生成树重构树的节点权沿根方向不升，比较方向相反。
- XOR 最小对、Borůvka 与 Trie 也能求 XOR-MST；选择方案时比较证明和复杂度，而非模板长度。
总结与自检
- 重构树内部节点表示什么事件？
- 两叶 LCA 权为何是首次连通阈值？
- 区间全部点连通为何只需相邻编号对？
- XOR 分治为何只需一条最小跨边？
- 去重为何不改变 XOR-MST 权值？
课后训练建议
先用逐步 DSU 暴力核对重构树 LCA 阈值，再完成区间 RMQ。XOR-MST 先对 8 个数枚举完全图 MST，对照递归拆分；卡住时只展开“最高位下界”，不要直接背 Trie 代码。最后阅读 Envy 的同权离线框架并写出临时 DSU 必须回滚的原因。