长链剖分学习笔记

长链剖分是一种将一棵树转化为一些链并在链上维护信息的算法

下面通过一些例子详细讲解长链剖分

维护 $k$ 级祖先

给定一棵树,要求 $O(1)$ 询问求 $x$ 点的 $k$ 级祖先

长链剖分顾名思义是以长度为剖分方式的,具体来讲,对于节点 $i$ 的长(重)儿子为向下能达到深度最深的儿子

我们可以通过类似重链剖分的方式两次DFS得出每一个节点的长儿子和它的链

通常来说,可以在每一个重链的顶点构建一个数组,即该条链上所有的点,这样总大小是 $n$ 的

求解 $k$ 级祖先就转化为往上跳到一条链然后通过该链的 $top$ 进行跳转

这些操作可以进行一些预处理后完成

维护DP信息

长链剖分通常用来维护与深度有关系的DP信息

具体实现是首先从重儿子处继承(右移一位,可用指针维护),然后暴力从所有轻儿子处更新,可以证明为 $O(N)$

一些例题