树链剖分

[[ slider_text ]]

[[ item.c ]]

发布时间 2023-06-25 作者：秋千月 来源：算法小站

线段树 dfs序 树链剖分

## 树链剖分的概念

**树链剖分**
把树分成若干条链，一般只考虑从根往下的链（树链一般不拐弯），保证每个点**只在一条链上**

换句话说，对于每个节点，都选一个儿子相连，分为**长链剖分**和**重链剖分**
**长链剖分**，选择一个儿子相连，使得这个儿子对应的子树中，有一个**深度最大的节点**
**重链剖分**，选择**`size`最大**的子树相连

一般用的比较多的是**重链剖分**
对于根节点`u`，找**`size`最大的子树**（子树对应的**儿子**是`v`），那么$$(u, v)$$ 是重边
和其他儿子相连的边都是轻边，同样`v`是**重儿子**，其他儿子是轻儿子
![](/media/content_img/heavy-light-decomposition-01.jpg)

> 树链剖分能解决什么问题

考虑一个节点`u`往上走到`root`，经过**轻边**，子树大小翻倍
> 证明，如果路径是轻边，假设当前经过的节点是`u`，那么`u`是轻儿子
   同时，`u`肯定有一个兄弟节点`v`是**重儿子**，满足`size(v) >= size(u)`
   沿着`u`再往上找到`u`的父亲`w`，那么 `size(w) = size(u) + size(v)`
   也就是说 `size(w) >= 2*size(u)`
   
沿着轻边走，最多只会有$$O(\log n)$$条轻边
对于任意两个点`u, v`的路径，轻边数量 $$\leqslant O(\log n)$$

考虑`u, v`的路径，它由**若干段重边**和若干条轻边相连而成，由于轻边数量最多是$$O(\log n)$$
由此重边最多有$$O(\log n)$$段（当然每一段也可能有很多条重边）
只需要用$$O(\log n)$$复杂度内，去维护**重链信息**，这样整个问题复杂度是$$O(\log ^ 2 n)$$的

**树链剖分大致流程**

* 第一遍 `dfs`，记录每个节点的父亲，深度，子树大小，重儿子节点编号

* 第二遍 `dfs`，求出每个点的**重链优先**`dfs`序，重链上的链头的元素
> 重链上的链头元素，类似于链的顶端（靠近`root`的顶端）
   重链优先，如果一个点有重儿子的话，要先`dfs`重儿子，链头不变
   （如果是轻儿子，链头就是轻儿子本身）
   
```bash
const int maxn = 1e5 + 10;
vector<int> dep(maxn, 0), pa(maxn, 0), 
    hs(maxn, 0), sz(maxn, 0);

vector<vector<int> > G(maxn);

// 第一遍dfs，求出深度，子树大小，重儿子，父亲
function<void(int, int)> dfs1 = [](int u, int fa) -> void {
    dep[u] = dep[fa] + 1;
    sz[u] = 1;
    pa[u] = fa;
    hs[u] = -1;

for (auto v : G[u]) {
        if (v == fa) continue;
        dfs1(v, u);

sz[u] += sz[v];
        if (hs[u] == 1 || sz[v] > sz[hs[u]]) {
            hs[u] = v;
        }
    }    
};

// 第二遍dfs，求出dfs序，重链上的链头元素
vector<int> l(maxn, 0), r(maxn, 0), 
    top(maxn, 0), id(maxn, 0);
int tot = 0;

function<void(int, int)> dfs2 = [](int u, int t) -> void {
    top[u] = t;
    l[u] = ++tot, id[tot] = u;

if (hs[u] != -1) {
        dfs2(hs[u], t);
    }
    for (auto v : G[u]) {
        if (v != pa[u] && v != hs[u]) {
            dfs2(v, v);
        }
    }

r[u] = tot;
};
```

## 树链剖分的重要性质
**性质一** 链头（top）绝对不可能是重儿子！它只能是轻儿子（或者是整棵树的根节点）
在一条重链上，除了链顶元素，其余所有元素都是它父亲的重儿子

> 证明如下，重链的定义是，从某一个点开始，不断选择它的重儿子一直往下走，直到叶子节点，这样串起来的一条路径叫重链。
如果你是重儿子，那么你会被“拉进”父亲所在的那条重链中
重儿子永远只是重链的“延续”，绝不可能成为一条重链的“开端”（链头）

> 由此，谁来开启新的一段重链呢？**只能是轻儿子**

**性质二**，自底向上，`(轻儿子 -> 父亲)`这样的边称为**轻边**
每经过一条轻边，子树大小翻倍

## 树链剖分求 LCA
**问题描述**
给定$$n$$个节点的树，有$$m$$个询问，对于每组询问，给定$$u, v$$
输出$$u, v$$最近公共祖先的编号

**算法分析**
考虑对于点$$u$$不断**往上跳**，如果是重链跳到**链头**，否则就跳一条**轻边**，即
$$u \to \text{top}(u) \to \text{fa(top}(u))$$

这样最终两个点都会跳到**一条链**上，LCA 就是**深度更浅**的点

> 那么问题是，应该跳哪一个点呢？

其实，我们可以看成每一次只跳一步，是重边就跳`u -> top(u)`，是轻边就跳 `u -> fa(u)`
每一次都要跳**链头深度更深的点**

> 这很好理解，将重边看作是一条边，这样每次我们只往上跳一步
  假设跳的过程是`u -> next(u)`，一定是选择 `next(u)`更深的往上跳
  
> 如果**链头**`top(u)`深度一样呢？那么 `top(u) -> fa( top(u) )` 一定是**轻边**
   跳哪个点其实都一样，都能跳到一起
   
```bash
LCA(u, v):
while top(u) != top(v):
	if dep(top(u)) < dep(top(v)):	v = fa( top(v) )
	else:	u = fa( top(u) )
	
if dep(u) < dep(v) return u
else return v
```

## 路径修改和查询
**问题描述**
给定$$n$$个节点，每个节点有一个权值$$w$$，现在有一些操作
* `1 u t` 将`u`点权值改成`t`

* `2 u v` 查询`u->v` 路径上的最大权值

* `3 u v` 询问从`u->v`路径上的节点权值和，包括`u`和`v`

**算法分析**
> 注意到两个点之间的路径，对应$$O(\log)$$段重链，如果对每段重链开一个线段树
   就对应每一个线段树的区间查询

注意到之前是按**重链优先**得到的`dfs`序，每一段重链的编号都是连续的
也就是说，重链对应**连续的一段区间**

如果对`dfs`序建线段树，**一段重链**就对应`dfs`序中的一段区间，这样就可以修改和查询了

> 问题是，怎么找到`u->v`对应的**重链路径**

类似于之前求`LCA`的过程，选链头更深的点往上跳，考虑 $$u \to \text{top}(u)$$
`top(u) -> u` 对应`dfs`序中 `[l(top[u]), ...,  l(u)]` 这一段区间
每跳一步就用这一段区间的信息来更新答案

两个点跳到一条链上的时候，再用`[l(u), l(v)]`这一段区间更新答案

**算法实现**
* 树链剖分求出重链优先的`dfs`序，用`dfn`记录

* 根据`dfn`数组建立线段树，那么我们有
  - 单点修改 `u->val`，线段树上执行`tr.set(l[u]-1, S{val, val})`
  （减`1`是因为线段树下标从`0`开始）
  - 区间查询，类似`LCA`的过程
  
```bash
while  top[u] != top[v]:
	if dep[ top[u] ] > dep[ top[v] ]: 	
		ans = op( ans,  [l[top[u]]-1, l[u]) ), u->pa[top[u]]
	else:	
		ans = op( ans, [l[top[v]]-1, l[v])] ),  v->pa[top[v]]

if dep[u] > dep[v]:		ans = op( ans, [l[v]-1, l[u]) )
else:	ans = op( ans, [l[u]-1, l(v)) )
```

**[SDOI2011 染色](https://ac.nowcoder.com/acm/problem/50487)**
**问题描述**
给定$$n$$个点的树，有以下操作
*  将 `a->b` 路径上的所有节点都染上颜色

*  询问`a->b`路径上的颜色段数量，比如`112221`有`3`段，`[11], [222], [1]`

**算法分析**
树链剖分的框架大致不变，问题是，如何统计信息？
线段树维护信息 `{ lc, rc, cnt }`，其中`lc, rc`分别表示左右端点的颜色
`cnt` 维护区间内**颜色的段数**，特别地，如果颜色都相同，`cnt = 0`

> 线段树如何合并信息？

`S op(S a, S b)` 函数返回 `S{a.lc, b.rc, a.cnt+b.cnt+(a.rc != b.lc)}`
**特别地**，如果一段内颜色**都相同**，区间的`cnt`值设为`0`（这样边界情况简单很多）
（这样最后统计答案的时候，一整个序列的颜色段数要记得`+1`）

`F`和`S mapping(F, S)`如何定义？
`F`涉及区间修改，可以定义为二元组`(mul, add)`，改成 `col`颜色对应`(0, col)`
这样单位变换也容易定义，`ID = (1, 0)`

`S mapping(F f, S x)`，映射操作，实际上修改后的颜色是
`{lc*f.mul+f.add, rc*f.mul+f.add, 0}`

`int comp(int f, int g)`，即作复合变换$$f(g(S))$$，`(fmul*gmul,  fmul*gadd+fadd)`

> 树链剖分如何维护信息

* 路径 `u->v` 的修改操作，套用树链剖分的框架
  沿着 `u -> fa( top(u) )` 往上跳的时候，线段树修改区间 `[ l(top(u))-1, l(u) )`
  （因为线段树维护的下标从`1`开始）
  当 `u, v` 跳到同一条链上的时候，线段树修改区间 `[ l(u)-1, l(v) )`
  
*  查询操作，注意**考虑顺序**，`ans`初始化为`{ 0, 0, -1 }`
   这是因为`0`是哨兵，之前的操作**没有**`0`这个颜色，所以`ans`和颜色相同的一段并起来
   会让`cnt += 1`，新的段的`cnt`恰好是`0`，很好地解决了边界问题
   
*  查询操作，用`ansu, ansv`分别表示`u, v`到`LCA`的两条链，需要分别计算，最后合并
   `u->top(u)`这条链的信息，和`dfs`序是**反的**，而相应的`lc, rc`也应该反过来
   
*  统计的时候，`v->top(v)`往上跳，对应查询`dfs`序的`[l(top(v))-1, l(v))`
   这个顺序刚好和`u->v`的路径**方向一致**，因为是往上跳，相当于在`ansv`的**前面接了一段**
   所以`ansv = op( [l(top(v))-1, l(v)), ansv )`
   而 `u->top(u)` ，`[l(top(u))-1, l(u))`方向和路径**方向相反**
   统计`ansu`的时候可以像`ansv`一样做，只不过`ansu`中的信息和实际的是**相反的**
   
   合并`ansu, ansv`的时候，对于`ansu`的`lc, rc`要取反
   返回`{ ansu.cnt+ansv.cnt+(ansu.lc != ansv.lc)+1 }`
   （`+1`是因为如果一整段颜色都相同，我们统计时候是按`0`统计的，实际上应该是`1`）
   
> 记一下代码中容易错的地方
   `S mapping(F f, S x)` 容易写错，当`f.mul == 0`的时候，是修改操作，新的`cnt = 0`
   如果`f.mul == 1`，那么表示单位变换，要令`cnt = x.cnt`
   返回 `{ lc = f.mul*x.lc + f.add,    rc = f.mul*x.rc + f.add,    cnt }`
   
## 子树的修改和查询
**[软件包管理器 NOI2015](https://ac.nowcoder.com/acm/problem/17882)**
**问题描述**
给定一个`0`号点为根的**有跟树**，一开始整棵树中所有点的权值都是`0`，给定两种操作

* `install x`，把`x->root`路径上的所有点都从`0`变成`1`
* `uninstall x`，把`x`及其子树中的所有点都从`1`变成`0`

每种操作，输出有多少个点发生了变化？即从`0`变成`1`或者从`1`变成`0`
原来是`0`的再设为`0`，被视为不变

**算法分析**
考虑树链剖分，对于`uninstall x`操作，只需要找到`x`所在的子树即可
这就对应`dfs`序中`[l(x), r(x)]`，在`dfs`序线段树中执行区间修改，修改为`0`

`install x` 操作呢？这时候不需要两个点一起跳了，只需要令 `x -> pa[ top[x] ]`
直到跳到根节点，跳的过程中执行区间修改 `[ l(top[x]), l(x) ]`，将区间全部改成`1`

> 线段树如何维护信息？

线段树需要维护`{cnt, sz}`，其中`cnt`表示区间中`1`的个数，`sz`表示区间中节点的个数
映射算子`F`定义为`F{ mul, add }`
如果将区间值全部设为`1`，`cnt = cnt*0 + sz`，此时`F{0, sz}`
如果将区间值全部设为`0`，`cnt = cnt*0 + 0`，此时`F{0, 0}`
单位变换是`F{1, 0}`

> 如何统计信息

只需要记一下`last`，表示上一次**整棵树**有多少个值为`1`的点
然后执行线段树**根节点查询**，当前整棵树有`res = all_prod().cnt`个节点
那么 $$|last - res|$$ 就是答案，然后更新`last = res`继续

上一篇：树上问题，DSU on Tree，启发式合并下一篇：树上问题综合

看完文章有啥想法