树上问题

[[ slider_text ]]

[[ item.c ]]

发布时间 2023-06-11 作者：zhangminchen 来源：算法小站

树上问题 dfs序 欧拉序 树上倍增

## 树上倍增
### 一些简单的应用

**求 u 的 k 级祖先**
简单来说，就是$$u$$往上走$$k$$步能走到哪里？将$$k$$拆成二进制
```bash
for j = log(n) to 0
    if (k >> j & 1):  u = up(u, j)
```

**统计路径信息**
针对**没有修改**的路径统计信息，以最小值，最大值为例
`up(u, j)` 表示$$u$$往上走$$2^j$$能到达的点
`val(u, j)`记录$$u$$网上走$$2^j$$**所经过的边**的最小值

二者都可以预处理得到
```math
val(u, j) = \min (val(u, j-1), \ val(up(u, j-1), j-1))
```

查询的话，用一个全局的`ans`记录最小值，一开始$$ans = +\infty$$
往上跳的时候，需要同步更新`ans`
```bash
ans = min(ans, val(u, j))
u = up(u, j)
```

**问题描述**
给定$$n$$个点的树，每条边给定边权，给定$$q$$个询问，每个询问
问路径$$u, v$$的最小值

**算法分析**
用前面提到过的算法，在算`LCA`的时候顺便计算最小值，值的注意的是，倍增法有两步
* 将`u, v`提至同一深度，默认`dep[v] > dep[u]`，此时需要将`v`这个节点提至相同深度
  实际上记`k = dep[v] - dep[u]`，就是求`v`的`k`级祖先，当`k>>j&1`时，
  记录的时候，更新`ans = min(ans, val(v, j))`

* 将`u, v`同步往上提，此时`ans = min{ans, val(v, j), val(u, j)}`

## 树的 dfs 序
按照 `dfs` 经过的每个点顺序，依次给每个点标号，它有一些性质
*  `dfs` 序中，每个点它的**子树标号是连续的**

**dfs 序能解决的问题举例**
对于一个点`x`，查询根到 `x` 路径上的点权和

如果一个点`x`的权值是`a[x]`，考虑`x`的**贡献**，`x`及其子树所在的区间是$$[l_x, r_x]$$
那么对于$$[l_x, r_x]$$中的**所有节点**，它到根的路径都会经过`x`
如果我们维护答案数组，$$\forall u \in [l_x, r_x]$$，都有`ans[u] += a[x]`

这样只要对每个节点$$x$$，在答案数组中，执行区间$$[l_x, r_x]$$加，加上`a[x]`
查询`x`到根路径的点权和，对应单点查询`ans[x]`

>  该问题可以用树状数组解决，用树状数组维护答案`ans`的**差分数组**
   这样对应`add(l[x], a[x]),  add(r[x]+1, -a[x])`
   单点查询`ans[x]`，对应树状数组求前缀和`sum(x)`
   
**值的注意的是**，树状数组的单点修改，比如将 `a[x]`修改成`y`
需要转换成**差值**，**增加或者减少**
实际上，`a[x] + (y - a[x]) = y`，也就是说，令`d = y - a[x]`，然后执行单点增加
`tr.add(x, d),  a[x] = y`

**dfs 序的算法实现**
```bash
vector<int> l(n+1, 0), r(n+1, 0);

int tot = 0;
function<void(int, int)> dfs = [&](int u, int pa) -> void {
	l[u] = ++tot;
	for (auto v : G[u]) {
		if (v == pa) continue;
		dfs(v, u);
	}
	r[u] = tot;
};
```
**其中**，`l[u]`记录了树的节点`u`在`dfs`序中的**下标**

## 树的 dfs 序（换根）
**问题描述**
给定$$n$$个节点的树，每个点有点权$$w_i$$，给定$$q$$个操作

`1 x y` 将`x`的点权改成`y`
`2 x` 询问`x`点的子树的点权和
`3 x` 将树的根换到`x`的位置

**算法分析**
> 难点在于换根，换根`dfs`序会变

做的时候，换根不需要改变`dfs`序，直接在原树的`dfs`序上做，根据根节点的位置分类讨论
我们需要标记一下**当前的根是谁**，不妨设为$$root$$，在查询$$x$$的子树时候
*

如果$$root = x$$，那么$$x$$子树的点权和，就是**整棵树**
   
*  如果$$root$$是$$x$$的后代，假设$$x$$有一个儿子$$y$$，并且$$r$$在**分支**$$y$$对应的子树中
   此时有$$l(x) < l(root) \ \textbf{and} \ r(x) \geqslant r(root)$$ 
   实际上，此时`y`这个分支变成了`x`的祖先了，`x`的子树点权和变成了
   整棵树去掉$$[l_y, r_y]$$这一段
   
*  其他情况，点权和依然是$$[l_x, r_x]$$这一段

> 还有一个难点，怎么找$$y$$
  如果我们把$$x$$的儿子$$i$$的`dfs`序编号，用$$[l_i, r_i]$$维护起来
  实际上我们要在$$x$$的儿子节点中找到一个$$y$$，使得
  $$y$$ 是**最后一个满足**$$l(y) \leqslant l(root)$$ 的点，对应
  `auto [ly, ry] = *prev( upper_bound( son[x].begin(), son[x].end(), PII(l[root], r[root] ) )`
  整棵树扣除 $$[l_y, r_y]$$ 这一段即可
  
上述信息都可以树状数组维护

## 欧拉序

**算法概述**
有时候用倍增求`LCA`并不能满足查询量非常大的场景，比如要求$$O(n \log n)$$ 次$$u, v$$距离
求两点间距离一般是`dep[u] + dep[v] - 2dep[ LCA(u, v) ]`，希望能够在$$O(1)$$内求出`LCA`

**欧拉序**，**括号序**
欧拉序和`dfs`序差不多，只需要`dfs`的时候，把**回溯时**经过的点也记录下来
（`dfs`序只在节点第一次被访问的时候记录）

![](/media/content_img/dfs-01.jpg)

如图所示，值得**注意的是**，欧拉序需要把**访问到的节点**都记录下来，但**叶子结点**一般**只需记一次**
图中，子树`4`中`9`这个点只需要记一次即可

**括号序**
括号序是`dfs`的时候，一个点入栈的时候记为`(`，出栈的时候记为`)`，叶子结点要记**两次**
叶子结点在括号序中，分别对应`( )`，因为入栈，出栈都要记一下

**欧拉序的使用场景**
欧拉序还需要记一下每个点的深度`dep(u)`
$$u$$第一次出现的时间戳记为$$p_u$$，$$v$$第一次出现时间戳记为$$p_v$$
那么`u, v`的`LCA`一定是 $$[p_u, p_v]$$ 区间内**深度最小的点**

这样就可以把`LCA`转换成`RMQ`问题

**欧拉序的算法实现**
具体到实现上，因为需要找到 $$[p_u, p_v]$$ 中`dep`最小的点，同时，还需要返回`LCA(u, v)`
所以建`ST表`的时候，可以考虑存储二元组`(dep[u], u)`，根据`pair`来建`ST`表
这样求最小值就是比较第一关键字`dep`

另外，这里给出欧拉序的算法实现
```bash
vector<PII> ord(2*n, PII(inf, 0));
vector<int> p(n+1, 0), dep(n+1, 0);

int tot = 0;
function<void(int, int)> dfs = [&](int u, int pa) -> void {
	dep[u] = dep[pa] + 1;
	p[u] = ++tot, ord[tot] = PII(dep[u], u);

for (auto v : G[u]) {
		if (v == pa) continue;
		dfs(v, u);
		ord[++tot] = PII(dep[u], u);
	}        
};
```

上一篇：可持久化权值线段树下一篇：树上问题，DSU on Tree，启发式合并

看完文章有啥想法