Kruskal 重构树
这是一种用于处理与最大/最小边权相关的一个数据结构。
其与 kruskal 做最小生成树的过程是类似的，我们考虑其过程：
按边权排序，利用并查集维护连通性，进行合并。
如果我们在合并时，新建一个节点，其权值为当前处理的边的权值，并将合并的两个节点都连向新建的节点，那么就可以得到一颗重构树。
例如下列数据生成的重构树：
4
1 4 2
2 3 4
1 3 1
3 4 3
黑色代表节点编号，红色代表其权值。
其满足一些性质：
-
这是一个二叉树，也是一个二叉堆
-
两点 \(\mathrm{LCA}\) 的权值即是这两点联通的 最小/最大 代价/时间。
-
对于一个限制，找到某个点最高的祖先 \(S\) 满足这个限制，那么 \(S\) 所在子树都满足此限制，并且此子树下所有叶节点在此限制下全部联通。
由于这些性质，kruskal 重构树常常与树剖/树上倍增放一起，做到每次 \(O(\log n)\) 的神秘操作。
以 Qpwoeirut and Vertices - 洛谷 为例：
给出 \(n\) 个点，\(m\) 条边的不带权无向连通图，\(q\) 次询问至少要加完前多少条边 \([L, R]\) 中的所有节点联通。
这是非常板的题，边权也就是其编号。
设 \(f(x)\) 表示 \(x\) 和 \(x + 1\) 联通的时间，那么所求也就是 \(\max_{x = L}^{R - 1} f(x)\)，这只需要求出 \(f(x)\) 随便维护一下即可。
那么求 \(x, x + 1\) 的联通时间，找到他们在重构树上的 \(\mathrm{LCA}\)，返回其编号即可。
或许其考点就是知不知道重构树，如果会了重构树，那么就简单了。
按照边权从大到小建出重构树，那么在当前水位下可联通的部分（整棵子树）也就很好求。
求这部分到固定的终点的最短路径？跑一次 DJK，然后把重构树看作一颗线段树，节点保存的也就是子树内最小的距离，在查询的时候利用倍增跳一跳就行了。
标签：重构,联通,Kruskal,30,最小,节点,边权 From： https://www.cnblogs.com/jeefy/p/17761104.html