首页
kruskal 重构树 学习笔记
性质
约定两个点
\(p,q\)
的
"麦ax值"
定义如下。设
\(p\)
到
\(q\)
的一条路径贡献是路径上
最大的边权
,则其 "麦ax值" 为
\(p\)
到
\(q\)
的众多路径中贡献最小值。
原图的节点都是重构树的
叶子
节点。
任意两个节点的 LCA 就是此两点在原图上的 麦ax值。
一个点的点权是
其子树中的点权
最大值。
性质2和3的推论:一个点的子树中,任意两点的 麦ax值 都小于此点的点权。
知识点乐
相关
标签