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