拖延了一个月,终于可以开始整理啦!
由于太长怕把AcWing炸了……
树论总结中的树链剖分一部分新建一个帖子。
树链剖分是处理树上问题的重要工具,用于将树分割成若干条链的形式,以维护树上的路径信息。
对树链剖分的学习由一道题开始:
对一棵有 n 个节点,节点带权值的静态树,进行三种操作共 q 次:
- 修改单个节点的权值
- 查询 u 到 v 的路径上的最大权值
- 查询 u 到 v 的路径上的权值之和。
保证 1≤n≤30000 , 1≤q≤200000 。
于是就诞生了树链剖分
树链剖分笔记
目录:
- 树链剖分的作用。
- 树链剖分的种类。
- 树链剖分的相关定义。
- 树链剖分的实现。
- 树链剖分两个DFS的代码。
- 树链剖分的性质。
- 树链剖分的常见应用。
现在开始介绍树链剖分
- 树链剖分的作用:
- 需要一个强大的能够对树上的数据统一处理的工具,于是
有些很烦的人发明了树链剖分。 - 具体来说,将整棵树剖分为若干条链,使它组合成线性结构,然后用其他的数据结构维护信息。
- 需要一个强大的能够对树上的数据统一处理的工具,于是
- 树链剖分的种类:
- 树链剖分具有多种形式,如:
- 重链剖分
- 长链剖分
- 实链剖分
- 大多数情况下(没有特别说明),树链剖分指的都是重链剖分,这也是最常用的。
- 树链剖分具有多种形式,如:
- 树链剖分的相关定义:
- 重子节点:对于一个节点,重子节点就是其子节点中子树最大的子节点。有多个最大就任取一,没有子节点就无重子节点。
- 轻子节点:对于一个节点,轻子节点是除重子节点外的剩余所有子节点。
- 重边:从一个节点到它的重子节点的连边。
- 轻边:从一个节点到其它轻子节点的连边。
- 重链:若干条首尾相连的重边组成的链。
-
把落单的节点也当作重链,那么整棵树就被剖分为若干条重链。
若不理解的话可以看下图:
- 树链剖分的实现:
- dfs1第一次DFS:
- 记录每一个节点的父节点。
- 记录每一个节点的深度。
- 记录每一个节点的子树大小。
- 记录每一个节点的重子节点。
- dfs2第二次DFS:
- 记录每一个节点的链顶(即所在重链的顶),应当初始化为节点本身。
- 记录每一个节点在重边优先遍历的时候的DFS序。
- 记录DFS序所对应的节点编号(与上一点相互映射)。
- dfs1第一次DFS:
- 树链剖分两个DFS的代码:
- fax是x的父亲。
- depx是x的深度。
- sizx是x的子树大小。
- sonx是x的重儿子。
- topx是x的链顶。
- dfnx是x的DFS序。
- rnkx是DFS序对应的节点编号,因此rnkdfnx=x
void dfs1(int o) {
son[o] = -1;
siz[o] = 1;
for (int j = h[o]; j; j = nxt[j])
if (!dep[p[j]]) {
dep[p[j]] = dep[o] + 1;
fa[p[j]] = o;
dfs1(p[j]);
siz[o] += siz[p[j]];
if (son[o] == -1 || siz[p[j]] > siz[son[o]]) son[o] = p[j];
}
}
void dfs2(int o, int t) {
top[o] = t;
cnt++;
dfn[o] = cnt;
rnk[cnt] = o;
if (son[o] == -1) return;
dfs2(son[o], t); // 优先对重儿子进行 DFS,可以保证同一条重链上的点 DFS 序连续
for (int j = h[o]; j; j = nxt[j])
if (p[j] != son[o] && p[j] != fa[o]) dfs2(p[j], p[j]);
}
- 树链剖分的性质:
- 树上的每个节点都属于且仅属于一条重链。
- 在剖分时重边优先遍历,最后树的 dfn 序上,重链内的 dfn 序是连续的,按 dfn 序排序后的序列即为剖分后的链。
- 一颗子树内的 dfn 序是连续的。
- 可以发现,当我们向下经过一条轻边时,所在子树的大小至少会除以 2。因此,对于树上的任意一条路径,把它拆分从 lca 往两边走,分别最多走 O(log n) 次,因此,树上的每条路径都可以被拆分成不超过 O(log n) 条重链。
- 树链剖分的常见应用:
- 路径上维护。例如用树链剖分求树上两点路径权值和,由于链上的 dfs 序是连续的,可以使用线段树、树状数组维护。每次选择深度较大的链往上跳,直到两点在同一条链上。这样跳链的操作适用于维护,统计,修改路径上的其他信息。
- 子树维护。有时会要求,维护子树上的信息,比如将以 x 为根的子树的所有节点的权值增加 。由于子树中节点的 dfs 序是连续的。那么子树信息就可以转化为一段区间信息。
- 最近公共祖先:不断向上跳重链,当跳到同一条重链上时,深度较小的点即为 lca。
终于结束了
容易发现经过重链剖分,一段重链的节点和一个子树的节点 dfs 序都是连续的,因此可以直接用线段树等维护区间信息的数据结构维护。——2023.7.20
既然来了又滑到底部,看到这里还不赞一个?
图好像是借鉴oiwiki的哦
厉害,只不过你学这些有什么用啊!?
树链剖分可以拿来吃全世界就我不会树剖是吧
讲的非常清楚
这个还缺一些结尾哦,比如说最后怎么维护,用线段树怎么维护等等问题
问题是我就是这个不会……还在搞
感谢提醒,会加入的
简单来说就是你把你经过的路径变成了数组上的一段一段的区间,然后区间和可以用线段树维护
嗯嗯,谢谢