树链剖分的相关概念

树链剖分： 树链剖分是一种思想，它可以通过给树中每个点重新编号，使得我们可以将树中任意一条路径转化成 $O(logn)$ 段连续区间。这样就能将树上路径的问题转化成区间问题，再用求区间问题的方法去进行处理。

树链剖分的原理

首先定义几个树链剖分中的概念。

重儿子： 对于任意非叶子节点 $u$，它的子节点中所在子树节点个数最多的子节点称为 $u$ 的 重儿子，若有多个所在子树节点个数最多的节点，则任选一个作为重儿子。

轻儿子： 对于树中的所有节点，除去根节点和所有重儿子，剩余的全部节点都是 轻儿子

重边： 树中任意重儿子和它的父节点之间的边称为 重边

轻边： 对于树中的所有边，除去重边，剩余的所有边，剩余的所有边都是 轻边

重链： 树中所有极大的由重边构成的路径被称为 重链，树中每个点都要在一个极大重链中，如果某个点不和重边相连，则自成一个重链。每个重儿子一定在它父节点所在的重链中，每个轻儿子一定在从它往下的重链中。

对于一棵树，我们直接通过它的 $dfs$ 序将其变成一个序列，这个序列就是在 $dfs$ 的过程中按顺序遍历到的每个点的次序，从根节点开始，遍历的过程中要求优先遍历整棵子树的重儿子，最开始一定会按照子节点的重儿子一直往下走，直到重儿子遍历完后，一步一步的回溯，回溯的过程中再将没有遍历到的子树遍历，过程中只要遇到重儿子就优先遍历，再进行回溯。

根据优先遍历重儿子而得到的 $dfs$ 序能保证所有重链中节点的编号都是连续的，在此前提下就有以下这个关键的定理

定理：

树中任意一条路径均可拆分成 $O(logn)$ 条重链，即 $O(logn)$ 个连续区间

由于该定理的证明对解题没有任何帮助，这里不再赘述，可以自行查找文献。

以上就是树链剖分的全部思想，整个流程并不复杂，简单来说，先用一个 $dfs$ 标记出每个节点的重儿子，再用一个 $dfs$ 找出所有的重链并标记出每个节点所在重链的顶点，同时还能得到整棵树转化成的优先遍历重儿子的 $dfs$ 序。到此我们就将整棵树转化成一个序列，并标记出了每个重链，接下来就需要将任意一条路径拆分成 $O(logn)$ 条重链。

转化的过程类似于求最近公共祖先的做法，假设我们想求 $(u, v)$ 之间的路径，设 $u$ 所在重链的顶点是 $x$，$v$ 所在重链的顶点是 $y$，看一下 $x, y$ 哪个更靠下，每次将更靠下的那一段重链拆分出来，假设此时 $x$ 更靠下，此时 $x$ 到 $u$ 的路径已经被拆分出来，然后就需要从 $x$ 走到下一段路径中，也就是 $x$ 的父节点 $fx$，然后在找出 $fx$ 所在的重链的顶点 $z$，再去判断 $z$ 和 $y$ 哪一个更靠下，再将靠下的一段重链拆分出来，以此类推。最终，这两个顶点一定会走到某一条公共的重链上，这条重链就是这两个顶点的最近公共祖先所在的重链。我们再将这两个点在重链上中间的一部分抠出来，就能得到 $O(logn)$ 条重链。

综上所述，我们就将每条路径拆分成了 $O(logn)$ 条重链，然后就能再通过其他处理区间问题的数据结构去进行维护。一般我们处理这些区间问题的时间复杂度都是 $O(logn)$ 的，每一个询问又拆分成 $O(logn)$ 个连续区间，因此每个询问的时间复杂度是 $O(log^2n)$ 的。

另外，对于 $dfs$ 序还有一个特点，任意一棵子树中的所有节点的编号是连续的，因此对于任意一棵子树同样可以转化成一段连续的区间，因此如果想对某一个子树中的节点进行操作，就可以直接转化成区间操作来处理。