长链剖分常用于优化一类特殊的动规，它可以在满足某些要求时，将$O(n)$的转移复杂度均摊为$O(1)$。
此外，长链剖分还有一些优秀的性质，但目前长链剖分在信息学竞赛中应用并不广泛。
定义
长链
长链的概念与重链类似。
点$x$的长链指从点$x$出发，到达其最深的后代所经过的路径。
重儿子
$x$所在的长链上的儿子称为重儿子。称为长儿子总觉得有什么不对
长链剖分
长链剖分的概念与重链（树链）剖分类似。
通过树上存在的长链，将树剖分为若干条不相交的路径。
顶点
称树上一条长链深度最小的点为该长链的顶点。
性质
性质$1$
对树长链剖分后，树上所有长链的长度和为$O(n)$。
此性质显然成立。
性质$2$
任意一个点$x$的$k$级祖先$y$所在长链长度一定$\ge k$。
证明：
- 若$x,y$在同一条长链上：
显然成立 - 若$x,y$不在同一条长链上：
因为不在同一条链，所以别的子树一样深或更深，结论依然成立。
应用
由于长链剖分根据深度大小进行剖分，因此可以解决一些与深度有关的问题。
应用$1$：$O(n\log n)-O(1)$在线询问一个点的$k$级祖先
首先花费$O(n\log n)$的时间预处理出ST表。
接着对树进行长链剖分，记$Len(x)$为点$x$所在长链长度。
对于每一个长链的端点$x$，求出其$\sum\limits_{i=1}^{Len(x)}$级祖先与$\sum\limits_{i=1}^{Len(x)}$级重儿子。
因为性质$1$，预处理时空复杂度均为$O(n)$。
同时预处理出$1\rightarrow n$每个数二进制表示最高位的$1$，也就是$highbit$，时间复杂度$O(n)$。
对于每次询问$x$的$k$级祖先，首先利用ST表跳跃到$x$的$2^{highbit(k)}$级父亲$y$处，令$r=highbit(k)$，显然有$k-r\lt r$。
根据性质$2$，有$y$所在长链长度$\ge r\gt k-r$，因此有$y$所在的长链顶点预处理的表一定包含$x$的$k$级祖先。
因此可以做到$O(1)$回答询问。
例题
应用$2$：$O(n)$统计每个点子树中以深度为下标的可合并信息
这个应用的思想十分类似Dsu on tree。
思想是当前结点直接继承重儿子的信息，轻儿子信息暴力统计。
因为长链剖分的特殊性，因此这个应用仅限于以深度为下标。
更一般的就只能使用Dsu on tree做到$O(n\log n)$的复杂度了。
更具体地：
若需求出点$x$的信息，首先从重儿子继承。
因为以深度为下标，因此只需要对数组进行移位即可。
后面我们会提到移位的实现方法。
接着，轻儿子的信息暴力合并到当前的信息中。
时间复杂度$O(n)$。
分析如下：
每个点$x$只会暴力统计其所有轻儿子的信息，而每个轻儿子的信息大小为该轻儿子所在长链长度。
而当递归到$x$的父节点$fa(x)$时，若$x$不是$fa(x)$的重儿子，则$fa(x)$会暴力统计大小为$x$长链长度的信息。
故，每个长链只会对转移的复杂度做一次大小为其长度的贡献。
因此根据性质$1$，总时间复杂度为$O(n)$。
移位的实现方法：
本处仅提到一种实现方式，但方法不只有这一种。
用指针维护动规数组，在重儿子传递给父亲时将指针左移/右移一位。（左移还是右移根据转移方程决定）
而给其他轻儿子分配不相交的内存即可。
不难发现，这样实现的空间复杂度仍为$O(n)$。
特别注意，这样实现也有相应的缺点，即若动规的数组高于一维，那么数组是一次性的，不能在完成转移后查询中间过程的值。
原因是部分内存被共用掉了。