树上问题综合

[[ slider_text ]]

[[ item.c ]]

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

DSU on Tree 树链剖分 树上差分 树的重心

## 树上差分
**[松鼠的新家 JLOI2014](https://ac.nowcoder.com/acm/problem/20139)**
**问题描述**
给定$$n$$个节点的树，给定一条路径$$a_1, a_2, \cdots, a_n$$，每经过一个节点
这个节点上的计数器都会`+1`，询问对于任意一个节点`i`，它会被经过多少次？
也就是最后这个节点计数器的值

**算法分析**
这个问题分析起来并不难，只需要 $$a\_i \to a\_{i+1}$$ 路径上的所有点都`+1`即可
为了解决边界问题，还需要将 $$a\_{i+1}$$ 单点修改，这个点的权值`-1`
![](/media/content_img/diff-on-tree.jpg)

用`tag(u)`表示树上差分的标记，差分操作需要令 `tag(u) += d, tag(w) -= d`
值的注意的是，给路径上所有点都`+d`，和给`u`子树所有点都`+d`
在最后统计答案的时候有所**不同**

* 给路径上所有点都`+d`，假设`LCA`是`w`，如图所示，`u -> w  （不包括w）`
  路径上所有点的子树都包括`u`，统计每个点子树的`tag`和
  刚好能够满足 `u->w （不包括w）`路径上所有点的权值都`+d`
  
  而`w`再往上（包括`w`），这些点的子树同时包含`u, w`两个点
  计算子树`tag`和的时候，`+1, -1`相互抵消，这些点的权值恰好不变
  
  至于不在`u->w`这个分支上的点，没有影响，综上所述，我们就完成了
  `u->w (不包括w)`路径上所有点都`+d`这个操作

* 给 `u` 及其子树中的所有点都`+d`，最后统计的时候
  需要计算每个点到根节点路径的`tag`和
  
  注意到`u`及其子树中所有点，到根的路径，都会经过`u`
  当`tag(u) += d`，统计这些点到根的路径的`tag`之和的时候，点权也都会`+=d`
  而其他点到根的路径不会经过`u`，没有影响
  
> 还有一个问题就是 `LCA` 这个边界如何处理？

假设我们要令 `u -> v` 路径上所有点都 `+d`
假设点`u`的**初始权值**是`val(u)`，先考虑差分标记 `tag(u)`

*  执行树上差分，令 `w = LCA(u, v)`，使得 `tag(u) += d,  tag(v) += d, tag(LCA) -= 2d`

*  `LCA` 处执行单点修改 `val(LCA) += d`
   （有时候`u -> v`路径不包括`v`，需要对`v`也进行单点修改 `val(v) -= d`）
   
*  `dfs` 统计每个点及其子树的`tag`和

*  对于每个点，`val(u) + tag(u)` 就是答案

### 树上差分的综合应用
**[天天爱跑步 NOIP2016](https://ac.nowcoder.com/acm/problem/16427)**
**问题描述**
给定一个$$n$$个点的树，有$$m$$个玩家，每个玩家沿着路径$$(s_i \to t_i)$$走
每一名玩家都是从$$0$$秒开始，一秒走一条边

现在每一个节点有一个**计数器**，第$$i$$个点的值$$w_i$$表示
如果在$$w_i$$秒**恰好**有一个玩家经过节点$$i$$，那么计数器会`+1`
现在问最后，每个节点的计数器值是多少？（记录了多少个玩家？）

**算法分析**
对于路径问题统计，可以考虑树上差分，假设路径是$$(u \to v)$$，`w = LCA(u, v)`
可以拆成两条路径，$$u \to w\_{\text{son}}$$，$$w\_{\text{son}} \to v$$，`LCA`的答案单独统计
(`w = LCA` 的儿子记为`son(w)`)

> 现在考虑路径$$u \to w\_{\text{son}}$$，假设路径上有一个观察点$$v$$
> 什么时候计数点`v`会做出记录（答案会`+1`）？

不妨记从$$u$$点出发的起始时刻是$$T_u$$，一开始$$T_u = 0$$，`v`的答案会`+1`**当且仅当**
*  `v` 在路径 `u -> son(w)`上

*  $$T\_u + \text{dep}\_u - \text{dep}\_v = W_v$$，即有

$$T_u + \text{dep}\_u = W_v + \text{dep}_v$$ 成立
   
> 这样，问题转换成
   对于每一个$$v$$，求出满足条件的$$u$$，并统计从$$u$$出发经过$$v$$的路径

记$$g(v) = W_v + dep_v$$，$$f(u) = T_u + dep_u$$，对于每个$$v$$，只需要
* 找到满足$$f(i) = g(v)$$的所有点$$i$$

* 并且把以$$i$$为起点，路径会**经过**$$v$$的，这样的$$i$$给选出来，统计即可

> 但这还是很难做，因为以$$i$$为起点，路径经过$$v$$，这样的$$i$$一定在$$v$$的**子树**中
   但是，以$$v$$的子树中的点为起点，有的路径并不一定会经过$$v$$
   
> 需要把路径问题转化成子树问题

类似**树上差分的标记思想**，考虑路径$$u \to v$$，注意到对于节点$$u$$
在$$0$$时刻，有一位玩家以$$u$$为起点**向上**走，**权值**为$$1$$

在点`w = LCA(u, v)`处，添加一个**哨兵**
在$$dep_u - dep_w$$时刻，**哨兵**以$$w$$为起点**向上**走，**权值**为$$-1$$

这样，如果我们统计**子树权值和**，就可以发现
从`w`点往上（包括`w`），`+1, -1`恰好抵消了，这样做的话
可以把所有$$u$$点往上的路径（不确定终点在哪里）
拆成**两段**权值分别是`+1, -1`的，到**根节点**的路径

> 这样拆分的话，以$$i$$为**起点**往上，路径经过$$v$$，这样的$$i$$就一定在$$v$$的子树中

对于每个点$$v$$，已知$$g(v) = w_v + dep_v$$
我们需要在$$v$$的**子树**中，找到**满足条件**的所有的$$i$$，计算它们的**权值和**（用$$wgt$$表示）
```math
\displaystyle
ans(v) = \sum_{i \in subtree(u)}  wgt(i)，\quad (\forall i: T_i + dep_i = g(v))
```
特别地，向上的链一开始$$T_i = 0$$

> 分析到这里差不多就可以做了

有$$m$$个人，每个人的路径是$$(u_i \to v_i)$$，先考虑某个人的起点$$u$$，拆点
$$(u, f(u), wgt) = \left< (u, T_u + dep_u, 1) \cup (w, T_w + dep_w, -1) \right>$$

其中$$w$$是`LCA(u, v)`，$$T_u = 0, T_w = dep_u - dep_w$$，从而一个人的起点$$u$$可以拆成
$$(u, f(u), wgt) = (u, dep_u, 1) \cup (w, dep_u, -1)$$

现在每个点$$v$$有一个**询问**，要在$$v$$的子树中找到
满足$$f(i) = g(v) = W_v + dep_v$$的，所有的点$$i$$的**权值之和**

> $$v$$的子树信息统计，可以用 Dsu on Tree，或者是用`dfs`序来做

用`dfs`序来做，我们要找出满足条件的点 $$i$$，其中
```math
\begin{cases}
l_v \leqslant l_i \leqslant r_v \\
f(i) = g(v)
\end{cases}
```
对于每个点$$v$$，用一个二元组$$(g(v), l_v)$$来表示，以$$g(v)$$为第一关键字排序
排序之后，对于某个点$$v$$要统计答案，只需要考虑**一段区间**

$$(g(v), l_v, wgt) \leqslant \cdots \leqslant (g(v), r_v, wgt)$$

计算这段区间内的点的$$wgt$$权值和即可

> 三元组计算区间权值和，和前缀和类似，假设问题中的三元组用`up[i]`表示

```bash
for (int i = 0; i < m; i++)
	s[i+1] = s[i] + up[i][2];
	
这样的话，考虑区间 [l, r]，对应 s 中的下标是 [l+1, r+1]
求区间[l, r]的和，实际上是 s[r+1] - s[l]

int pl = lower_bound( { w[v]+dep[v], l[v], -2 } )
// 选择 -2 为第三维，因为 wgt = {1, -1}，这一维选-2，一定能把 wgt = -1 的情况考虑到

int pr = lower_bound( {w[v]+dep[v], r[v], 2} )
// 选择 2 为第三维，因为我们要的是 s[r+1] 而不是 s[r]

ans[v] += s[pr] - s[pl];
```

> 上升链解决了，下降链呢？

下降链是对称的，考虑到达**链的终点**$$u$$的时间是$$T_u$$
下降链上的点$$v$$能被观察到，当且仅当
$$v$$在路径上，并且$$T_u - (dep_u - dep_v) = W_v$$，从而
$$T_u - dep_u = W_v - dep_v$$

那么对应的，令 $$T = dep\_u + dep\_v - 2dep\_{lca}$$，`w = LCA(u, v)`
$$(f(u), u, wgt) = \left< (T-dep_u, u, 1) \cup (T-dep_u, w, -1) \right>$$
和上升链是对称的

值的注意的是，`W[w] == dep[u] - dep[w]`的时候，对`LCA`单独统计，`ans[w] += 1`

## 树上启发式合并
**[CCPC Changchun 2020 F,  Strange Memory](https://codeforces.com/gym/102832/problem/F)**
**问题描述**
给定$$n$$个点的有根树，每个点$$i$$有权值$$a_i$$，现在需要找到**不同**的点对$$(i, j)$$
（特别地，$$(i, j), (j, i)$$算同一对），点对必须满足
```math
a_i \oplus a_j = a_{\text{lca}(i, j)}
```
要求满足上面条件的点对的异或和，$$\sum\_{i = 1}^{n} \sum\_{j=i+1}^{n} (i \oplus j)$$

**算法分析**
考虑`Dsu on Tree`，枚举`w = LCA`，哈希表维护重儿子，枚举轻儿子
假设当前枚举的轻儿子是`v`，我们要在重儿子中尝试找到`u`，满足
$$a_u = a_v \oplus a_w$$

不妨记 $$val = a_v \oplus a_w = a_u$$，这样哈希表中，**查询**`a[u] = val`，使得
$$mp[val] = \left< u_1, u_2, \cdots, u_k \right>$$

> 最暴力的方法，当然是把`[u1...uk]`分别和`v`取异或，再加起来
  有没有比较简单的做法？
  
异或问题，可以**每一位**分别考虑，然后针对每一位来算贡献
对于第`j`位，哈希表记 `cnt[ val ][ j ][ 0/1 ]`，表示重儿子中，**满足条件**的`u`
第`j`位是`0/1`的数有多少个？

> **特别注意**，这里的`0/1`指的是`u`的第`j`位而不是`a[u]`的第`j`位
换句话说，`cnt[ a[u] ][j][ u>>j&1 ]`

比如`v`的第`j`位是`1`，那么只需要考虑满足条件的`u`中，第`j`位是`0`的
所以 $$ans += 2^j \cdot cnt(val, j, 0)$$ 即可

> Dsu on Tree 合并的时候，把轻儿子扔到哈希表中， `cnt[ a[v] ][j][ 0/1 ] += 1` 即可

## 树链剖分的应用
**问题描述**
给定一棵动态树，维护两种操作

*  `0 u delta`，`u`的子树中的每个节点都会长出`delta`个果子

*  `1 k u1 v1 ... uk vk`，求出 `ui->vi` 路径上果子数的和，如果路径有交叉
   交叉点的果子只计算一次
   
**算法分析**
第一种操作是子树加，可以用标准的树链剖分和线段树解决
第二种操作，需要求一堆树链的并，可以用**虚树**来实现，虚树实际上就是树上的离散化
对于一条链，只取端点和`LCA`，即`(u, v, LCA(u, v))`，然后根据这些点来建树

当然，更直观的方法，是使用**树链剖分（heavy-light-decomposition）**
第二种操作，实际上是给定了$$k$$条链，注意到树链剖分，可以把一条链转化为$$O(\log n)$$个区间
实际上，$$k$$条链对应$$O(k\log n)$$ 个子区间

$$k$$条链的并，可以转化成$$k$$个区间的并，当求出这些区间的并之后
用线段树或者树状数组，转化成若干个区间的**求和**

> 如何转化成**若干个区间**？树链剖分的时候，当两个点不在一条链上
  比如 `dep[ top[u] ] < dep[ top[v] ]`，此时跳链 `v -> fa[top[v]]`
  
>  就把对应的区间 $$[ l(top(v)), l(v) ]$$ 存到待合并的区间中，其中$$l(v)$$表示点$$v$$的`dfs`序编号

## 树链剖分综合问题
**[CSP-S 2019 树的重心](https://ac.nowcoder.com/acm/problem/54640)**
**问题描述**
对于一个大小为$$n$$的树，定义树的重心为$$c$$，当且仅当删去$$c$$及与它关联的边之后
分裂出的所有子树大小$$\leqslant \lfloor \frac{n}{2} \rfloor$$
对于包含至少一个节点的树，它的重心只可能有$$1$$个或$$2$$个

现在给定一棵树$$S$$，问单独删除每一条边之后，分裂出的两个子树的重心**编号和**

```math
\displaystyle
E(u, v)= 
\sum_{1\leqslant x \leqslant n, \ x 号点是 Su' 的重心} x + \sum_{1\leqslant y \leqslant n, \ y 号点是 Sv' 的重心} y
```
求出 $$\sum E(u, v)$$

**树的重心**
树的重心可以根据定义求出，`dfs` 的过程中，维护每个点的**最大子树的节点个数**`wgt[u]`
如果`wgt[u] <= N/2`，那么就标记`u`是重心

```bash
const int maxn = 1e5 + 10;

// sz: 用于维护节点大小（u 及其子树上所有节点个数）
// wgt: 维护所有子树中，最大的子树节点数，即这个节点的重量
// cent: 存储树的重心的节点编号（可能有 2 个）

vector<vector<int> > G(maxn);
vector<int> sz(maxn, 0), wgt(maxn, 0), cent(2, 0);

// N 是整棵树的节点数
function<void(int, int, const int)> dfs = [](int u, int fa, const int N) -> void {
    sz[u] = 1;
    wgt[u] = 0;

for (auto v : G[u]) {
        if (v != fa) {
            dfs(v, u, N);
            sz[u] += sz[v];
            wgt[u] = max(wgt[u], sz[v]);
        }
    }
    wgt[u] = max(wgt[u], N - sz[u]);

if (wgt[u] <= N / 2) {
        cent[ cent[0] != 0 ] = u;
    }
};
```

**算法分析**
> 重心如何去维护？

对于一棵树，如果根节点$$x$$不是重心的话，那么重心一定在$$x$$的**重儿子里**
证明，假设$$x$$为根的树的大小是$$n$$，并且$$x$$不是重心，那么$$x$$一定有一个儿子$$u$$
满足 $$\text{size}(u) \geqslant \lceil \frac{n}{2} \rceil$$，而其他儿子$$\text{size} < \frac{n}{2}$$
所以$$u$$一定是$$x$$的重儿子

> 递推地去想，如果$$u$$还不是重心，重心就一定在$$u$$的重儿子中

对整棵树进行重链剖分，那么重心一定可以沿着**重链** $$x \to u_1 \to u_2 \cdots \to u_k$$ 找到

> 这条重链上的重心，要满足什么特征？

假设在**重链**上找到一个点`u[i]`是重心，对于 `u[i] -> u[i+1]`，我们有
```math
\displaystyle
\text{size}(u_i) \geqslant \lceil \frac{n}{2} \rceil, \quad \text{size}(u_{i+1}) \leqslant \lfloor \frac{n}{2} \rfloor
```
> 如果不满足的话，那么 `n - size(u) >= floor(n/2)`，`u`往根方向的子树大小太大了
  `u` 也不是重心
  
> 可能有双重心，判断一下`u`的父亲是否也满足条件即可

把重链抽出来，因为重链上`size`是**递减**的，可以考虑在重链上二分

> 现在有动态删边操作，假设删除了边$$(u, v)$$，$$v$$**往下（往它的子树方向走）**部分是不变的
 
> $$v$$往下走的**重链**，仍然是整棵树，根节点往下的重链的一部分，那么难点是
  怎么求$$v$$**往上走（根节点方向）**的子树的重心？ 
  
可以考虑**换根**，同时维护轻重链剖分，可以一边`dfs`一边维护，对于$$(u, v)$$
比如`dfs(u, fa) -> dfs(v, u)`，我们就令**整棵树的根节点**从`u`换到`v`，同时维护相关信息

换根其实不难，因为每一次`dfs`的时候，只和**儿子**换根，考虑换根`u->v`
换根之前，$$\text{size}(u) = n, \quad \text{size}(v) = S_v$$，换根之后
$$\text{size}(u) = n - S_v, \quad \text{size}(v) = n$$，其他点不变

只需要考虑更改`u, v`的轻重链剖分的信息即可

* `u`节点原来的重儿子是`w`，`u->v`换根之后，**重儿子没有被换成根**
  那么换根后`root = v`，`u`的重儿子**还是`w`**，不需要更新`u`的轻重链剖分信息
  （但是要改一下`size`信息）
  
*  `u`节点的重儿子`v`**被换成了根**，那么`u`点的重儿子是谁？
   对于`u`来说，需要找一个**新的重儿子**，`for`一遍`u`所有的儿子就可以了
   `v`点的重儿子是谁？**不一定是`u`**，`for`一遍`v`所有的儿子找出来
   
> 每个点只有当重儿子变成父亲的时候，需要`for`一遍所有儿子
  而重儿子只有$$O(\log n)$$个，所以这样做复杂度是$$O(n \log n)$$
  
> 最后一个问题，怎么在重链上二分？

可以考虑**倍增**，记$$go(u, j)$$表示$$u$$沿着**重链**往下跳$$2^j$$步跳到的点
不妨记$$u\prime = go(u, j)$$

如果$$\text{size}(u \prime) \geqslant \lceil \frac{n}{2} \rceil$$，那么就往下跳，否则就不跳

注意到，树上倍增的话一般要求**树的结构不会发生变化**，但本题中，树的结构会变
幸运的是，可以**一边`dfs`一边维护倍增表**

换根的话，从`u->v`，变化的位置，要么是之前的根，要么是新的根
如果在`u, v`**子树中**跳，（在我们还没有`dfs`到子树的时候）**子树中跳的位置**不会变
换根只需要维护`u, v`的倍增表即可

**算法实现**
重点的瓶颈在于，只有$$O(\log n)$$个重儿子，所以只能针对`u`的重儿子被换成根的时候
才可以尝试去`for u 的所有儿子`，找到**新的重儿子**
但`dfs`还原现场的时候，不能每一次都`for`一遍去找**新的重儿子**，否则会退化到$$O(n^2)$$

对于换根$$u \to v$$，维护好`size[u], size[v]`之后
如果`size[u] >= size[ hs[v] ]`，可以直接标记`hs[v] = u`，然后更新`v`的倍增表

对于查询操作，`query(v)`，在`v`为根的**子树中**，倍增找到满足$$\text{size}(w) \geqslant \lceil \frac{n}{2} \rceil$$的点
并且`w`的两个子树`max{ sz(hs[w]), sz(v) - sz(w) } <= sz(v)/2`，`w`就是重心
然后我们在检查一下`w`的父亲是不是重心即可，注意此时`w == v`的话，`w`是没有父亲的

**注意**
![](/media/content_img/hld-001.jpg)

如图所示，记重链上的边为**关键边**，如果我们删的边$$(u, v)$$**不是关键边**
我们是不需要重新`for u, v 的儿子`来找`hs[u], hs[v]`的，否则算法复杂度会退化成$$O(n^2)$$
如果删的边**不是关键边**，那么`hs[u], hs[v]`是相对不变的，只需要处理关键边的情况

* 假设换根`u->v`，并且`hs[u] = v`，即`(u, v)`是**关键边**
那么对于`u`，需要`for`一遍`u`所有儿子，找出新的**重儿子**，同时更新`u`的倍增表
   
*  注意到原树的根`r`到`v`的这一段倍增表，暂时用不到了（图中蓝色部分）
   那么`v`的倍增表**要不要改**呢？
   如图所示，当且仅当$$v\to u$$沿着红色路径往下走的时候，需要更新`v`的倍增表
   换言之，如果$$(v \to u)$$ 是一条**轻边**，我们没必要更改`v`的倍增表和`hs[v]`，因为不会变
   
*  当且仅当$$v \to u$$是一条**重边（关键边）**的时候，需要重新计算`v`的倍增表
   此时有 `size[u] >= size[ hs[v] ]`，我们直接标记`hs[v] = u`，并且更新`v`的倍增表

上一篇：树链剖分下一篇：codeforces数据结构专题（一）

看完文章有啥想法