只略略讲一点基本方式与思想了
-
构建
并查集,边按从小(大)到大(小)加入,建新点,点权为此边权,该点为两点根的父亲。 -
性质:(此处为最小生成树重构树)
1.lca(u,v)为u到v路径上的最大边权
2.类似大根堆
3.显然的性质,叶子为点,非叶子映射边
2024-03-28 20:10:46
只略略讲一点基本方式与思想了
构建
并查集,边按从小(大)到大(小)加入,建新点,点权为此边权,该点为两点根的父亲。
性质:(此处为最小生成树重构树)
1.lca(u,v)为u到v路径上的最大边权
2.类似大根堆
3.显然的性质,叶子为点,非叶子映射边