Warning
由于本博客作者实在是太弱啦，本篇文章可能存在大量的错误，漏洞，不规范，不合法之处。若您发现本文章所存在的任何问题，请您尽快在评论区指出，十分感谢！
另外，本文随意转载，但请注明出处。
前置
在阅读本篇文章之前，你至少应该了解并初步掌握以下知识：
同时若你了解以下知识，它们会帮助你理解：
- 树形 dp
- dfs 序
问题
我们有时会遇到这样的问题：
给定一棵节点数为 n 的树，对于每个节点，具有一个点权 w[i]，有 m 次操作：
- change u t 将节点 u 的点权设为 t
- qmax u v 询问 u 到 v 路径上的最大点权
- qsum u v 询问 u 到 v 路径上的点权和
n≤30000 q≤200000 保证任意时刻 w[i] 在 [-30000,30000]...
思考
看到问题，我们一定会发现，这和序列操作的问题十分相似... 所以我们考虑用线段树维护点权来解决问题，我们需要构造一种映射关系，使得树上的点与线段树维护的一维序列满足某种对应关系。
暴力编号的想法很明显的，然而不足之处也是很显然的... 这样更新一个点权是\(O(log_2^{n})\) 的复杂度，然而，当我们查询某个路径的时候... 我们需要枚举 u->v 间的所有节点，这样做的复杂度是树的直径... 退化为了暴力的\(O(n)\) 复杂度... 所以我们需要考虑一种具有良好性质的映射关系，使得复杂度能在各种情况下都得到保证...
我们考虑对某些点一起处理，将一棵树剖分成若干条链，这种剖分方案是满足复杂度要求的，对于每一条链，用数据结构去维护它。
这就是树链剖分
定义
在介绍树链剖分前，你需要了解以下概念~
- 重儿子：对于节点 x 而言，它的重儿子 son[x] 即它的儿子中子树最大的节点
- 轻儿子：对于节点 x 而言，它的非重儿子均为轻儿子
- 重边：对于节点 x 而言，它与它的重儿子 son[x] 间的边即为重边
- 轻边：非重边均为轻边
- 重链：连续相连重边所构成的链即为重链
请熟悉以上概念，它们将在下面的讲解中被反复提及
树链剖分
我们通过以上定义划分这棵树后，显然，一条从 u 到 v 的路径是由一些重链和一些轻边组成的，对于以上划分方式，有一个很良好的性质：
- 对于一条从节点 x 到根节点的路径，最多有\(log_2^{n}\) 条重链和\(log_2^{n}\) 轻边
Comments | NOTHING