构造方法

按照Kruskal的传统步骤，先排序，按顺序枚举两个非连通块，合并后， 建一个点权为两点之间边权的父节点 。这样建出来的一棵树称为Kruskal重构树。
e.g. 假设原图（盗的）长这样：

建成树后就是这样（蓝色实线为最小生成树）：

用途

Kruskal重构树可以维护诸如“查询从某个点出发经过边权不超过w的边最远所能到达的节点”或“从某点到某点所有路径的最长（短）边的最小（大）值”（即最小（大）瓶颈路）之类的问题。
总之，算法处理范围有限，且多为同时包含“最大最小”、离线可二分的题目。
可与数据结构结合，以维护更复杂的数据结构。
支持在线，单次复杂度为\(O(\log n)\)。

性质

按照上述方法建出来的树有一些非常好的性质。
1.树上除叶子结点以外的点都对应着原来生成树中的边，叶子结点就是原来生成树上的节点。
2.由于新点的创建顺序与原来生成树上边权的大小有关，可以发现，从每个点到根节点上除叶子结点外按顺序访问到的点的点权是单调的。
3.出于Kruskal算法贪心的性质，两个点u和v的LCA的点权就对应着它们最小生成树上的瓶颈。
4.实际上这棵树就是一个二叉堆。

例题

[简单]NOIp2013 货车运输
Solution：先bb一句，最大值最小叫最小瓶颈路，但这题是最小值最大，干脆叫最大瓶颈路吧（口胡中
那这题就是最大瓶颈路果题了。

[较难]NOI2018 归程

Kruskal重构树

原文：https://www.cnblogs.com/wzzyr24/p/11802816.html