Kruskal 重构树详解及其应用

Kruskal 重构树是一种在图论中用于解决最小生成树问题的算法。它基于Kruskal算法，通过将最小生成树中的边转换为树结构，从而提供了一种新的视角来分析图中的路径和节点关系。Kruskal重构树具有以下几个关键性质：1. 它是一棵二叉树；2. 按最小生成树建立时，它是一个大根堆，反之亦然；3. 所有的叶子节点是原图中真实存在的点，而非叶子节点则是虚拟节点；4. 在原图中，任意两点之间所有路径的最大边权的最小值，等于最小生成树上这两点路径间的最大边权，同时也是Kruskal重构树上这两点的最近公共祖先（LCA）。Kruskal重构树的基本应用包括直接求解最大边权最小值或最小边权最大值问题。进阶应用则涉及利用Kruskal重构树作为瓶颈来处理更复杂的树上最小-最大问题。Kruskal重构树的复杂度主要受限于排序步骤，为O(n log n)。在具体应用中，如P1967 [NOIP 2013 提高组] 货车运输问题，可以通过建立最大生成树的重构树并求出LCA来解决最小边权最大值问题。而在星际导航问题中，则建立最小生成树的重构树来求最大边权最小值。更复杂的应用如P9638 「yyOI R1」youyou 的军训问题中，Kruskal重构树被用作瓶颈来限制条件，通过DFS统计叶子节点数量来回答问题。