Kruskal 重构树

前言

做题，遇到这个东西不会，来学一下

现在有一个 $n$ 个点的无向图，求出它的最大生成树（也可以是最小生成树，若是最小生成树，则将后文的所有大小关系反转，性质依然成立）后，可以用如下方式得到它的 Kruskal 重构树：

从大到小枚举树边；
维护一个并查集，设这条树边为 $(u,v,w)$ ， $u,v$ 在并查集中的祖先分别为 $u',v'$ ，则新建一个点 $x$ ，连接 $(u,x)$ 和 $(v,x)$ 两条边，并使 $x$ 的点权为 $w$ ，在并查集中将 $u,v$ 的祖先设为 $x$ 。

性质 1：建出的重构树符合二叉小根堆的性质，即每个点的点权均小于等于其儿子的点权。
性质 2：点对 $(u,v)$ 在原图中所有路径中，边权最小值最大的路径上的最小值 $=$ 最大生成树上， $(u,v)$ 两点路径上最小的边权 $=$ Kruskal 重构树上 $\operatorname{lca}(u,v)$ 的点权。
- 第一个等号显然。第二个等号，考虑加边过程，每次加边新建的虚点都联通了两个点集，而加入 lca 时便联通了 $u$ 和 $v$ 所在的点集，故使 lca 加入时的那条边一定在 $u$ 到 $v$ 的路径上。而由性质 1 得，lca 的点权最小，且不存在另一条在路径上且边权小于 lca 点权的边，即这条边是 $u$ 到 $v$ 路径上边权最小的边。
性质 3：由性质 2，对于给定的点 $u$ 和常数 $w$ ，设集合 $S=\{v\ |\ \operatorname{Min}(u,v)\geq w\}$ ，其中 $\operatorname{Min(u,v)}$ 代表 $u,v$ 在最大生成树上的路径上最小的边权，则所有 $S$ 中的点的 lca 为 $u$ 的所有祖先中深度最小的点权 $\geq w$ 的点。