Kruskal算法是把边从小到大加入,最终把所有点连成一个联通块。

Kruskal重构树就是同样把边从小到大加入,只不过是重构了一张图,新建了一些节点,这些节点有点权,对应的恰好是原图上的边。

这样我们就可以利用这新图的一些性质,比较关键的是 原图上的两点在重构树上的LCA的点权就是他们在原图的最小生成树上的简单路径的边权最大值

比较拗口,不过证明还是比较简单的,毕竟越浅的点意味着这个点是越晚加入的,也就意味着它的边权是它所在重构树上子树内点所构成的联通块内最大的。