Kruskal 重构树，顾名思义，就是利用 Kruskal 算法构造出的一棵新树。
（好像是句废话）
构造方式
给出一张图，构造其 Kruskal 重构树的方式和用 Kruskal 求其最小生成树的方式其实是差不多的。
我们维护一个 \(n\) 个点构成的森林。刚开始这个森林中没有一条边，每个点的点权均为 \(0\)。
接下来我们按照 Kruskal 的方式，从小到大考虑每条边。
对于一条边 \(u \to v\)，设 \(u\) 的树根为 \(ru\)，\(v\) 的树根为 \(rv\)。
如果 \(u\) 和 \(v\) 不在一棵树中，就新建一个点 \(p\)，\(p\) 的点权设为这条边的边权，然后连接 \(p \to ru\)，\(p \to rv\)（将 \(u\) 和 \(v\) 所在的集合并入新集合中）。
最后我们会得到一棵 \(2n-1\) 个点的树，这就是 Kruskal 重构树。
这棵树有什么特点呢？
- 整棵树都是二叉树，并且任意一个非叶子节点都有两个儿子（可以从合并过程来看出来）；
- 整棵树满足大根堆性质，即任意一个点的点权都比其子节点的点权大（仍然考虑合并过程）；
- 原图的最小生成树上两点间路径中的最大边权，等于重构树上两点最近公共祖先的点权（还是可以从合并过程中看出来）。
例题
可以拿来做一道 Kruskal 重构树的练手题。
建立最大生成树的 Kruskal 重构树（因为不保证联通，所以严格来说是重构森林），根据上面的性质 3，答案即为 \(\text{lca}(u,v)\)。
记得判断 \(u,v\) 不联通的情况。
代码在上面的题解里，这里就不贴了。
我们要找的是起点 \(s\) 能到达的所有点中，距离 \(1\) 号点最近的点。
先预处理 \(1\) 至其他点的最短路，随后以海拔为关键字降序排列所有边，建立 Kruskal 重构树。建树时同时处理一个点的所有子节点距离 \(1\) 号点的最近距离。
如果一个点 \(u\) 的点权大于水位线，则 \(u\) 子树内的所有点互相可达。
因此我们需要找到 \(s\) 的一个深度最浅的祖先，使得该祖先的点权高于水位线。这个可以通过树上倍增实现。
代码详见上面贴的题解。