一些定义
重子节点表示其子节点中子树深度最大的子结点
如果有多个子树最大的子结点,取其一。如果没有子节点,就无重子节点。
轻子节点表示剩余的子结点
从这个结点到重子节点的边为重边
到其他轻子节点的边为 轻边
若干条首尾衔接的重边构成重链
把落单的结点也当作重链,那么整棵树就被剖分成若干条重链。
如图(这种剖分方式既可以看成重链剖分也可以看成长链剖分):
一些性质
性质 1
从一个节点到根的路径的轻边切换条数是\(\sqrt{n}\)级别的
证明:
(我感觉有点不是很沾边?)
长链剖分 - sun123zxy - 博客园 (cnblogs.com)
「算法笔记」长链剖分 - maoyiting - 博客园 (cnblogs.com)
感觉↑这个要有道理一点?
长链剖分学习笔记 - Ynoi - 洛谷博客 (luogu.com.cn)
这个↑比较严谨
性质2
对于树上任意一点\(x\),它的\(K\)级祖先\(y\)所在长链的长度一定\(≥K\)
证明:
①当\(x\)在\(y\)所在的长链中,\(x\to y\)的距离都为\(K\)了,那么\(y\)所在长链的长度肯定\(≥K\)
②当\(x\)不在\(y\)所在的长链中
我们首先考虑为什么\(x\)不在长链中,肯定是因为有其他儿子的深度更大
所以肯定存在一些长链上的节点到\(y\)的距离\(≥K\),因此\(y\)所在长链的长度\(≥K\)
证毕。
(这不是显然吗)
求解
其实跟重链剖分很像
就把大小\(size\)改成深度\(dep\)就
标签:长链,cnblogs,剖分,笔记,重链,com,节点 From: https://www.cnblogs.com/yvette1217/p/17337286.html