长链剖分
长链剖分学习笔记。
简介
长链剖分，顾名思义，就是每条链都很长嘛！
跟树链剖分名字比较像，那他们有什么不同呢？
树链剖分重儿子靠子树大小。
那长链剖分靠啥呢？当然是靠最深的点谁更深啦。
那么求出 $len_u$ 表示最深的点到 $u$ 的距离就可以啦~
好了，我们已经会对一棵树进行长链剖分了。
长链剖分有点类似于 dsu on tree，解决的是一些跟树上启发式合并相关的题。
长链剖分需要题目满足一些跟深度有关的性质。比如树形dp合并时dp数组的下标只需要用到 $len_v$ 个之类的。
这个东西这样讲感觉比较难懂。具体看例题吧。
性质
性质1
任何节点的 $k$ 级祖先所在长链长度大于 $k$ 。
证明十分显然。
性质2
任何节点往上跳经过的长链条数最多为 $O(\sqrt{n})$ 条。
证明：每次跳长链长最多 $+1$，最坏情况为一直 $+1$。因此最多跳 $O(\sqrt{n})$ 条。
例题
dp题一般是先长链剖分，然后指针实现。