Kruskal 重构树是在无向图做最小生成树的 Kruskal 算法时可以同时构建出来的一棵树。
性质
事实上,这里的“重构”是针对原图的最小生成树而言的。
Kruskal 重构树用非叶子节点表示原图的最小生成树上的边,点权即为原图上的边权,用叶子节点对应原图中的节点,故 Kruskal 重构树节点数是 \(2n-1\)。(不要忘记开 \(2\) 倍空间)
由于一条边连接两个节点,故 Kruskal 重构树一定是一棵二叉树。
构建过程
我们在 Kruskal 算法过程中,若选定一条边作为图上的最小生成树边,就创建一个新节点代表这条边,左右儿子是这条边所连两个连通块的根节点。
也就是说,Kruskal 重构树的构建过程就是将 \(n\) 个散点通过添加 \(n-1\) 个公共祖先构建出来的,由于我们是在 Kruskal 算法过程中跑出来的,所以先加入的点(即深度较大的点)点权较小(事实上可以理解成是一个大根堆),同时可以得出一个性质:定义原图上两点间的距离为两点间路径的边权最大值,则原图中两点间距离的最小值就是 Kruskal 重构树上两点 LCA 点权。
若原图不连通,建出的就是 Kruskal 重构树森林。
例题
星际导航
板题,建出 Kruskal 重构树后直接查 LCA 即可。
[ONTAK2010] Peaks 加强版
从一点 \(u\) 开始只经过权值小于等于某个值 \(x\) 的边,相当于可以到达 Kruskal 重构树中包含 \(u\) 的、以权值小于等于 \(x\) 的节点为根的子树的所有叶子节点。可以直接倍增找到该子树的根。查询第 \(k\) 大可以直接拍到 dfs 序上用主席树做。
[NOI2018] 归程
我们以海拔为关键字降序排序,建出的 Kruskal 重构树满足:若水位线低于根节点权值,则子树内叶子节点在原图上相互可达。则此时花费为子树内所有叶子节点到达 \(1\) 号点距离的最小值。这个可以最短路预处理,建树时倍增维护到非叶子节点上。