type
status
date
slug
summary
tags
category
icon
password
通过两次DFS来对树进行处理。
其中第一次 DFS 统计出 节点的 父节点，子树节点个数，深度，重儿子。
第二次DFS统计出 节点 所在重链的顶节点，DFS序，DFS序对应的节点编号
重链剖分时根据DFS序建立线段树。
利用dfs序在线段树上的性质，每条重链在线段树上是连续的。
- 将树从x到y结点最短路径上所有节点的值都加上z
在寻找公共祖先的过程中，将预先存在线段树上的连续路径统一加上
- 求树从x到y结点最短路径上所有节点的值之和
与上个操作同理，在跳跃公共祖先的过程中，利用线段树求区间和
- 将以x为根节点的子树内所有节点值都加上z
易知，子树的DFS序在线段树上是连续的，而第一次DFS中统计出了子节点的个数，所以直接利用线段树区间加即可。
- 求以x为根节点的子树内所有节点值之和
同上述操作。
完整代码如下：
- Author:Grimner
- URL:https://tangly1024.com/article/example32
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!