在Kruskal的过程中同时维护Kruskal重构树,每加入一条边,建立一个新点,新点点权为原来的边权,其左右儿子就是连接的两个连通块根。
这样新建出的树,满足原树中两点路径之间最大值就是Kruskal重构树上两点的LCA,实现了从最值到确定值的转变。
所以常常由于求解“最小瓶颈路”问题。
例题:CF2021E3 Digital Village (Extreme Version) - 洛谷
在Kruskal的过程中同时维护Kruskal重构树,每加入一条边,建立一个新点,新点点权为原来的边权,其左右儿子就是连接的两个连通块根。
这样新建出的树,满足原树中两点路径之间最大值就是Kruskal重构树上两点的LCA,实现了从最值到确定值的转变。
所以常常由于求解“最小瓶颈路”问题。
例题:CF2021E3 Digital Village (Extreme Version) - 洛谷