kruskar重构树

只略略讲一点基本方式与思想了

  • 构建
    并查集,边按从小(大)到大(小)加入,建新点,点权为此边权,该点为两点根的父亲。

  • 性质:(此处为最小生成树重构树)
    1.lca(u,v)为u到v路径上的最大边权
    2.类似大根堆
    3.显然的性质,叶子为点,非叶子映射边

上一篇:jQuery选择器--:first和:last


下一篇:[题解] CF1540B Tree Array