类似于轻重链剖分,也有一种树链剖分方式叫做长链剖分,每次我们选子树深度最大的节点当做重儿子,注意这里子树深度是指一棵子树中所有结点的深度最大值。
有以下性质:
- 一个节点的 \(k\) 级祖先所在链的长度一定大于等于 \(k\)。
比较显然。因为如果小于 \(k\) 的话就会选从那个祖先到这个节点的路径当做重链。
- 所有链的总长是 \(O(n)\)
比较显然。因为重链不交,可以近似看做是对整个树的划分。
- 任意一个点向上跳跃重链的次数不会超过 \(\sqrt n\) 次。
我们一直向上跳,每次跳到的一个点所在重链长度最小是上个点的重链长度加 \(1\),所以我们一直经过的重链长度最多是 \(1,2,...\sqrt n\),由此可知性质得证。
求 \(k\) 级祖先
求 \(k\) 级祖先,长链剖分可以做到 \(O(n\log n)\) 预处理,\(O(1)\) 查询。
具体做法如下:我们倍增处理所有结点的祖先,然后对于每个链,设链长为 \(len\),处理出该链链顶向上,向下(顺着链向下)长度为 \(len\) 的每一个点。这是预处理。
对一个查询,设为 \(x,k\),表示我们要查询 \(x\) 的 \(k\) 级祖先,我们考虑设 \(r\) 为 \(k\) 的最高二进制位表示的那个二进制数,我们考虑寻找 \(x\) 的 \(2^r\) 祖先,由性质 \(1\),我们可以得到这条重链的长度一定是大于等于 \(2^r\) 的,这样我们就可以保证,我们要查询的点,一定是被我们预处理过了。所以我们可以通过判断被查询点和该链顶点的深度来进行 \(O(1)\) 的查询。
长链剖分优化 dp
具体方法是,我们在合并信息的时候,直接把重儿子的承接过来,其余儿子的信息暴力统计,这样做的话时间复杂度是 \(O(n)\) 的。
考虑证明。当一个儿子的信息被暴力统计时,这个儿子一定是其所在重链的链顶,那么合并这个儿子的信息的时间复杂度可以看做其所在重链的长度。
由此可以看出,总的暴力合并的复杂度不会超过链的总长,由此可以得到时间复杂度为 \(O(n)\)。
当然,大多是当这个 DP 与深度有关时才这么做,这样暴力合并的复杂度才不会超过链的总长。
标签:长链,剖分,祖先,复杂度,长度,重链 From: https://www.cnblogs.com/HeNuclearReactor/p/17552249.html