Kruskal 重构树

\(Kruskal\) 重构树

解决的基本问题：一张图中 \(u\) 到 \(v\) 路径上最大边的最小值。

构建：在从小到大加边的过程中，如果 \(u\), \(v\) 不在一个并查集中，就建立一个新的节点 \(X\)，并将 \(fu\) 和 \(fv\) 分别作为 \(X\) 的左右儿子， \(X\) 的点权就是这条边的边权。这样树，我们称为 \(Kruskal\) 重构树。

\(Kruskal\) 重构树有如下重要性质：

• \(Kruskal\) 重构树是一颗二叉树。
• 两点 \(u\) 和 $v $ 的最近公共祖先 $ LCA(u,v)$ 的点权为原图中从 $u $ 到 \(v\) 满足最大边最小的路径上的边的最大值。
• 任意点的权值大于左右儿子的权值，是一个大根堆（若边权从大到小排序，则为小根堆）。
• \(Kruskal\) 重构树整棵树的根就是最后所建的结点。
• 若原图不连通，即建出的是一个森林，那么就遍历每个节点，找到其并查集的根作为其所在树的根。

SOJ - Network：重构树板子

SOJ - 神奇的花园：重构树+启发式合并