有很多优秀性质的东西,应用场景比较明显
把 Kruskal 过程中,一次合并连通块的操作看作,建立一个边的虚点,把这个虚点和两侧连通块的根连起来,并成为新连通块的根
这样就可以把图变成一个二叉树,并且点权从浅到深是单增的,也就是大根堆,而且有且仅有实点是叶子
原图中『两个点路径上最大边权』的最小值,就是重构树上路径边权的最大值,即两点 LCA 的点权。
反过来,如果要找到 \(u\) 的最大边权最小值 \(\le w\) 的所有 \(v\),会发现是某个子树的所有实点(叶子)
实际应用起来不只跟边权有关系,很多时候需要想办法把点权转化成边权,再在重构树上研究原本的点权问题,标志是『找树 / 图上两点间的编号 / 点权最值』