只略略讲一点基本方式与思想了
构建 并查集,边按从小(大)到大(小)加入,建新点,点权为此边权,该点为两点根的父亲。
性质:(此处为最小生成树重构树) 1.lca(u,v)为u到v路径上的最大边权 2.类似大根堆 3.显然的性质,叶子为点,非叶子映射边
kruskar重构树
原文:https://www.cnblogs.com/bestime/p/15149903.html