长链剖分

发表于 2020-01-03 分类于总结

长链剖分学习笔记。

长链剖分，顾名思义，就是每条链都很长嘛！

跟树链剖分名字比较像，那他们有什么不同呢？

树链剖分重儿子靠子树大小。

那长链剖分靠啥呢？当然是靠最深的点谁更深啦。

那么求出 $l e n_{u}$ 表示最深的点到 $u$ 的距离就可以啦~

好了，我们已经会对一棵树进行长链剖分了。

长链剖分有点类似于 dsu on tree，解决的是一些跟树上启发式合并相关的题。

长链剖分需要题目满足一些跟深度有关的性质。比如树形dp合并时dp数组的下标只需要用到 $l e n_{v}$ 个之类的。

这个东西这样讲感觉比较难懂。具体看例题吧。

任何节点的 $k$ 级祖先所在长链长度大于 $k$ 。

证明十分显然。

任何节点往上跳经过的长链条数最多为 $O (\sqrt{n})$ 条。

证明：每次跳长链长最多 $+ 1$ ，最坏情况为一直 $+ 1$ 。因此最多跳 $O (\sqrt{n})$ 条。

dp题一般是先长链剖分，然后指针实现。