树链剖分

闲人 · 2021-08-27 11:47:21 · 个人记录

树链剖分

前置知识：

1. DFS续
2. 线段树

需要处理的问题：

• 将树从x到y结点最短路径上所有节点的值都加上z

• 求树从x到y结点最短路径上所有节点的值之和

• 将以x为根节点的子树内所有节点值都加上z

• 求以x为根节点的子树内所有节点值之和

概念

• 重儿子：对于每一个非叶子节点，它的儿子中 以那个儿子为根的子树节点数最大的儿子 为该节点的重儿子

• 轻儿子：对于每一个非叶子节点，它的儿子中 非重儿子 的剩下所有儿子即为轻儿子

• 叶子节点没有重儿子也没有轻儿子

• 重边：一个父亲连接他的重儿子的边称为重边 //原写法：连接任意两个重儿子的边叫做重边

• 轻边：剩下的即为轻边

• 重链：相邻重边连起来的 连接一条重儿子 的链叫重链

• 对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链 每一条重链以轻儿子为起点