Kruskal重构树一般用于求图上任意两点间距离的最值，距离为路径上边权最值。
建树：
将边权升序排序后，依次把点对加入树中，每次把两点当前所在的树根与一个新点连边，点权为原边权，然后新加的点成为树根。
例如，对于以下最小生成树：
它的Kruskal重构树为：
性质：
- 对于原图上的两点，它们的距离为重构树上两点的 \(\operatorname{lca}\)。
- 每个点的子树的点权都不大于它本身。
来点题目：P4768 [NOI2018] 归程
Kruskal重构树学习笔记
发布时间 2023-12-20 09:08:38作者: jr_inf