课前零食：把合并史写成树

并查集很擅长回答“现在是不是一伙”，却有一点健忘：所有人最终合并后，它不记得谁先握手、谁后入群。Kruskal 重构树的想法像给每次合并拍一张合影，并把合影按发生顺序叠成一棵树。

本节目标

学完后，你能：

手工按边权或时间运行 Kruskal，维护当前连通块；
发现普通 DSU 丢失“两个点第一次连通在何时”的历史；
在每次成功合并时新建父节点，构造 Kruskal 重构树（Kruskal reconstruction tree）；
用两原点的 LCA 读出首次连通阈值，并解释树上父亲权值为何单调；
区分最小生成树式递增处理与最大生成树式递减处理的阈值含义。

前置知识与课前自测

前置：无向带权图、Kruskal、并查集、树的祖先概念。LCA 的倍增实现可留到正式课。

Kruskal 扫到一条连接已在同一连通块内两点的边时，为什么跳过它？
边按权从小到大加入后，“1 和 4 连通”的最早时刻会不会晚于“1 和 4 最终连通”的时刻？
若 DSU 最后只剩一个根，能从父数组直接看出 2 与 4 在权值 5 才相遇吗？

先做判断：自测答案

1. 会在当前森林中形成环。2. 不会；最终连通只是说明某个有限阈值存在，最早时刻是更精确的信息。3. 通常不能：DSU 父亲只为快速 find 服务，路径压缩还会把过程抹得更干净。

互动规则：把“群聊合并”记成事件卡

用 1 到 5 五张人物卡和下列边卡：

(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。

停顿 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)). $$

不是因为 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 中。

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。它先让你预测 2 与 4 何时相遇，再逐条打印 Kruskal 边卡与新事件节点。可输入：

show：查看重构树的侧视图和每个节点的叶子数；
q 2 4：问两点的首次连通阈值；
at 2 3：问阈值 3 时 2 所在的原点集合；
at 2 6：比较同一点在更高阈值下的块。

先自己画祖先链，再让程序做 LCA；不要把“它输出 5”误当成已经理解了为什么是 5。

扩展与联系

重构树常用于按时间加边、按高度淹没、按温度连通等“单调合并”问题；权值不一定真是边长。
若边会删除，合并历史不再单调，普通重构树不能直接倒放维护。
对连续编号顶点区间，若能把“整个区间连通”化为相邻点阈值的最大值，可再接 RMQ/线段树；这是正式课的一条重要转化。
XOR-MST 也用 Kruskal 思想，但它的难点是不用显式列出完全图边；不要把它和重构树混成同一个模板。

总结与自检

重构树的叶和内部节点各代表什么？
为什么内部节点的两个孩子必须是当前 DSU 根？
两叶 LCA 的权值为什么是首次连通阈值？
递增版和递减版分别对应哪一种单调阈值？

自检答案

叶是原点、内部节点是一次成功合并；孩子是两个完整旧连通块；它是最早同时包含两叶的事件；递增版允许边权不超过 T，递减版保留边权至少 W。

一周预热安排

第 1 天：手做一次 Kruskal 泡泡合并，记录每个阈值的块。
第 2 天：不看答案画出 6、7、8、9 四张事件卡。
第 3 天：用 LCA 手答三对点的首次连通权。
第 4 天：运行互动程序，比较 DSU 最终状态与完整合并史。
第 5 天：进入Kruskal 重构树与 XOR-MST 正式课。

00-课前零食-把合并史写成树.md 12 KB Verlauf Originalformat