# 课前零食：把合并史写成树 > 并查集很擅长回答“现在是不是一伙”，却有一点健忘：所有人最终合并后，它不记得谁先握手、谁后入群。Kruskal 重构树的想法像给每次合并拍一张合影，并把合影按发生顺序叠成一棵树。 ## 本节目标 学完后，你能： - 手工按边权或时间运行 Kruskal，维护当前连通块； - 发现普通 DSU 丢失“两个点第一次连通在何时”的历史； - 在每次成功合并时新建父节点，构造 Kruskal 重构树（Kruskal reconstruction tree）； - 用两原点的 LCA 读出首次连通阈值，并解释树上父亲权值为何单调； - 区分最小生成树式递增处理与最大生成树式递减处理的阈值含义。 ## 前置知识与课前自测 前置：无向带权图、Kruskal、并查集、树的祖先概念。LCA 的倍增实现可留到正式课。 1. Kruskal 扫到一条连接已在同一连通块内两点的边时，为什么跳过它？ 2. 边按权从小到大加入后，“1 和 4 连通”的最早时刻会不会晚于“1 和 4 最终连通”的时刻？ 3. 若 DSU 最后只剩一个根，能从父数组直接看出 2 与 4 在权值 5 才相遇吗？
先做判断：自测答案 1. 会在当前森林中形成环。2. 不会；最终连通只是说明某个有限阈值存在，最早时刻是更精确的信息。3. 通常不能：DSU 父亲只为快速 find 服务，路径压缩还会把过程抹得更干净。
## 互动规则：把“群聊合并”记成事件卡 用 1 到 5 五张人物卡和下列边卡： ~~~text (1,2,2) (3,4,3) (2,3,5) (4,5,6) (1,5,9) ~~~ 边卡第三项是时间/权值。纸上画四栏：**对象**（当前有哪些群）、**状态**（每群的代表）、**动作**（拿起哪张边卡）、**账本**（本次真的把哪两群合并、时间是多少）。先别画一棵大树，先让 DSU 的健忘症露面。 ## 从零搭框架：DSU 会合并，但不会讲故事 ### 第 0 步：先按时间翻边卡 从小到大处理卡片。每次只问：两端现在在同一个泡泡里吗？若不在，就把两个泡泡画成一个更大的泡泡。 | 当前边 | 两端处理前的泡泡 | 选不选 | 处理后的泡泡 | |---|---|---|---| | (1,2,2) | | | | | (3,4,3) | | | | | (2,3,5) | | | | | (4,5,6) | | | | | (1,5,9) | | | | > 停顿 0：处理到权值 5 后，1 与 4 是否连通？处理到权值 3 后呢？请不要看最终结果再倒推。
展开：阈值连通的第一张表 权值 2 合并 {1},{2}；权值 3 合并 {3},{4}；权值 5 合并 {1,2} 与 {3,4}，此时 1、4 首次连通；权值 6 把 5 接入。最后 (1,5,9) 已在同一块，跳过。边权不只是代价，也可以读成“允许使用到何时”。
### 第 1 步：故意问 DSU 一个它答不好的问题 现在问：2 与 4 是在何时首次连通？如果你只保存普通 DSU 的最后父数组，所有叶子可能都指向同一代表；若开着路径压缩，连“先经过谁”也看不到。重跑一遍当然能回答一个询问，很多询问就会把相同历史反复回放。 > 停顿 1：在处理权值 6 后，若只留最终集合 {1,2,3,4,5}，你还区分得出 2-4 的首次连通时间和 1-5 的首次连通时间吗？缺的究竟是一个数，还是一段结构？
展开：缺的是合并的谱系 2-4 在 5 连通，1-5 在 6 连通。不是给每个点多存一个“最后时间”就能解决：一个点会和许多别的点在不同时间相遇。我们需要保存“哪个连通块在何时由哪两个旧块合成”的树状谱系。
### 第 2 步：每次合并，不选旧根当新根 第一次成功合并 1、2 时，拿一张新事件卡 6，写上权值 2；让它的孩子是原点 1、2。DSU 的新代表也改成 6。第二次成功合并 3、4，拿事件卡 7，写上 3。第三次合并两个大泡泡，拿事件卡 8，写上 5，孩子正是 6、7。最后拿事件卡 9，写上 6，孩子是 8、原点 5。 ![普通并查集只留下当前代表，重构树留下合并事件](../插图/06-最小与最大生成树/00-KRT-01-DSU与事件卡.svg) > 停顿 2：节点 8 的两个孩子为什么必须是 6、7，而不能直接接 1、2、3、4 四个叶子？若直接接四个叶子，丢失了哪两次发生在更早时刻的合并？
展开：内部节点是一次二元事件，不是一团成员清单 6 和 7 分别记录了权值 2、3 时已发生的合并。8 的含义是“在权值 5，这两个已连通块第一次成为同一块”；保留两个孩子才保留了嵌套时间。树的叶子仍是原点，内部节点才是事件。
### 第 3 步：把“何时相遇”翻译成最近共同事件 在刚画的树中，2 的祖先链是 2→6→8→9，4 的是 4→7→8→9。第一次相同的祖先是 8，卡上写 5。因此： $$ \operatorname{first\_connect}(u,v) = \operatorname{value}(\operatorname{LCA}(u,v)). $$ ![两片叶子的最近共同事件就是首次连通阈值](../插图/06-最小与最大生成树/00-KRT-02-LCA就是相遇.svg) 不是因为 LCA 有魔法，而是任何时刻 T 对应“删掉所有 value>T 的祖先连接”。u、v 在同一块，当且仅当它们已共同落在某个 value≤T 的事件节点下；最小这样的 T 就是它们最低的共同祖先权值。 ## 问题动机：把很多次时间旅行压成一次建树 若有 q 个问题，每个都问“两点在多大阈值后连通”或“阈值 T 时点 u 的连通块多大”，重跑 Kruskal 是 O(qm log m) 量级的重复劳动。重构树把所有阈值的合并历史一次性展开为至多 2n-1 个节点；随后用 LCA、祖先跳跃或子树信息查询。 ## 步步式引导：节点权的方向决定你问的阈值 ### 1. 递增 Kruskal：向根的时间不减 本节按边权递增处理。新事件一定发生在两个旧事件之后，所以从叶到根，节点权不减。对阈值 T，点 u 所在的“当前块”是 u 向上走、但不跨过 value>T 的最高祖先。它的叶子数可预先存在该祖先的 subtree_size 中。 ~~~text build_reconstruction_tree(edges in nondecreasing value): make every original vertex a DSU root and a leaf for (u, v, w) in edges: a = find(u); b = find(v) if a == b: continue event = new_node(value=w, children=[a, b]) DSU_parent[a] = event DSU_parent[b] = event DSU_parent[event] = event ~~~ 这里的 DSU 根不再一定是原顶点，它是“当前连通块在重构树中的根”。这正是实现中最容易写错的身份切换。 ### 2. 最大生成树式处理：方向反过来，故事不变 若按边权从大到小合并，内部节点权从叶到根不增。它适合问“只保留权值至少 W 的边，两点是否已连通”或最大瓶颈路径。不要机械套递增版的比较号：先在纸上写清 T 是“允许不超过”还是“允许至少”，再决定向祖先跳的条件。 > 停顿 3：若从大到小处理边，两个点的 LCA 权值 8，表示它们在保留权值至少多少的边时开始连通？阈值往更低还是更高移动会让连通块变大？
展开：最大版的读法 LCA 权 8 表示只允许权值至少 8 时，它们首次连通；把下限继续降低，会加入更多边，连通块只会变大。树仍在记录合并史，只是“时间轴”从大权向小权播放。
## 核心知识：三张账本要分开 | 账本 | 存什么 | 为什么不能省 | |---|---|---| | DSU | 当前每个连通块的重构树根 | 快速判断这条边是否带来新合并 | | 重构树 | 每次成功合并的两个旧根与权值 | 保留所有历史阈值 | | 树上预处理 | parent、depth、up、subtree_size | 快速求 LCA、跳到阈值位置 | 树最多有 n 个叶与 n-1 个成功合并节点；若原图不连通，会得到森林，常加一个虚根或按题目逐树处理。建立阶段排序 O(m log m)，DSU O(m α(n))；LCA 预处理 O(n log n)，每次两点阈值查询通常 O(log n)。 在一棵 MST 上，u 到 v 路径的最大边权也等于递增重构树 LCA 的权值：Kruskal 在该时刻恰把二者连起来。这是“最小瓶颈路径”与重构树相遇的地方；但不要反过来以为重构树本身就是原 MST，它记录的是合并关系，不保留被跳过的所有原边。 ## 实现指南 - 数组容量至少开到 2n；连通图最多生成 n-1 个内部节点。 - 一次合并创建 event 后，必须让两个**当前 DSU 根**的父亲改为 event；不能只写原边端点 u、v。 - 用重构树邻接表或 children 数组单独做 DFS/LCA；不要把 DSU 路径压缩后的父指针当树父亲。 - 若题目边权相同，多个合并节点权相同没有问题；“首次连通阈值”仍正确，树形可随同权处理顺序不同。 - 若要问阈值块大小，预处理每个重构树节点包含多少原叶；内部 event 的叶子数是两个孩子之和。 ## 纸上模拟：给每次握手一张合影 请把下表补完，再画 6、7、8、9： | 新节点 | 发生权值 | 左孩子 | 右孩子 | 覆盖的原点 | |---|---:|---|---|---| | 6 | | | | | | 7 | | | | | | 8 | | | | | | 9 | | | | |
展开：完整的合并史 6@2 的孩子是 1、2；7@3 的孩子是 3、4；8@5 的孩子是 6、7，覆盖 1,2,3,4；9@6 的孩子是 8、5，覆盖全部五点。2 与 4 的 LCA 是 8，首次相遇为 5；1 与 5 的 LCA 是 9，首次相遇为 6。
再设阈值 T=3、5、6，分别圈出点 2 所属的最高允许祖先。你应该得到 {1,2}、{1,2,3,4}、{1,2,3,4,5}。这就是“向上跳到不超过 T 的最高事件”的具体含义。 ## 互动小实验室 运行 [把合并史写成树.py](../../互动程序/06-最小与最大生成树/00-把合并史写成树.py)。它先让你预测 2 与 4 何时相遇，再逐条打印 Kruskal 边卡与新事件节点。可输入： - show：查看重构树的侧视图和每个节点的叶子数； - q 2 4：问两点的首次连通阈值； - at 2 3：问阈值 3 时 2 所在的原点集合； - at 2 6：比较同一点在更高阈值下的块。 先自己画祖先链，再让程序做 LCA；不要把“它输出 5”误当成已经理解了为什么是 5。 ## 扩展与联系 - 重构树常用于按时间加边、按高度淹没、按温度连通等“单调合并”问题；权值不一定真是边长。 - 若边会删除，合并历史不再单调，普通重构树不能直接倒放维护。 - 对连续编号顶点区间，若能把“整个区间连通”化为相邻点阈值的最大值，可再接 RMQ/线段树；这是正式课的一条重要转化。 - XOR-MST 也用 Kruskal 思想，但它的难点是不用显式列出完全图边；不要把它和重构树混成同一个模板。 ## 总结与自检 1. 重构树的叶和内部节点各代表什么？ 2. 为什么内部节点的两个孩子必须是当前 DSU 根？ 3. 两叶 LCA 的权值为什么是首次连通阈值？ 4. 递增版和递减版分别对应哪一种单调阈值？
自检答案 叶是原点、内部节点是一次成功合并；孩子是两个完整旧连通块；它是最早同时包含两叶的事件；递增版允许边权不超过 T，递减版保留边权至少 W。
## 一周预热安排 - 第 1 天：手做一次 Kruskal 泡泡合并，记录每个阈值的块。 - 第 2 天：不看答案画出 6、7、8、9 四张事件卡。 - 第 3 天：用 LCA 手答三对点的首次连通权。 - 第 4 天：运行互动程序，比较 DSU 最终状态与完整合并史。 - 第 5 天：进入[Kruskal 重构树与 XOR-MST 正式课](03-Kruskal重构树与XORMST.md)。