树上动态规划（路径问题）

[[ slider_text ]]

[[ item.c ]]

树上动态规划（路径问题）

发布时间 2024-05-16 作者：秋千月 来源：代码源

线段树 主席树 树上问题 树链剖分 树形dp

## 树上路径（简单）
**问题描述**
给定$$n$$个点的树，给定$$m$$条路径，每个路径有一个权值，现在要求选择一些路径
使得每个点最多在一条路径上（也就是路径不相交），要求路径权值和最大

### 算法分析
> 树形 dp 没有办法解决额外路径限制，考虑在 dp 状态中，加入路径这个维度

此类问题一般在 LCA 处考虑路径问题，$$dp(i, j)$$表示点$$i$$在路径$$j$$上，最大的路径权值和
转移考虑每个点在不在这条路径上，或者我们不选这个点
![](/media/content_img/treepath-01.png)
![](/media/content_img/treepath-02.png)
![](/media/content_img/treepath-03.png)

根据以上的分析，对于每个点$$u$$，`dfs(u)`的时候，先算$$dp(u, j)$$
然后用$$dp(u, j) \to g(u)$$，来更新$$g(u)$$

> 上述分析有点冗余，实际上我们并不需要$$dp(u, j)$$

怎么保证每条路径都被考虑到？我们对一条路径只考虑`LCA`
不去考虑每个点具体在哪条路径里，只在`LCA`处考虑这个点**选或者不选**
另$$dp(i) \leftarrow g(i)$$，表示所有在$$i$$这个子树中，没有伸出来的路径，最大的权值和

那么接下来考虑$$dp(u)$$的转移
经过$$u$$的路径，一条都不选，那么和前面分析相同，$$dp(u) = \sum (dp(v))$$

考虑$$u$$在我们选择的路径$$j$$里
![](/media/content_img/treepath-04.png)

### 算法实现
> 具体怎么去实现呢？

* 首先在`LCA`处考虑，这个比较容易实现，可以通过预处理所有的路径$$lca = (u, v)$$
  在求`LCA`的同时，把路径上的点都存在`vec`中
  因为**路径有权值**，可以用三元组`(u, v, ai)`来表示路径，挂载到点`lca`中，用`map[lca, (u, v, ai)]`对应起来
  也就是令`map[lca].push_back( (u, v, ai) )`
  
  这样，如果需要获取路径上的所有点，可以如下求
  ```bash
  auto get = [&](int u, int v, int LCA) -> void {
  		vector<int> res;
		while (u != LCA)  res.push_back(u), u = up[u][0];
		while (v != LCA)  res.push_back(v),  v = up[v][0];
		return res;
  };
  ```

* `dfs(u)`执行树形`dp`，首先`for 所有的儿子 v`，`dfs(v)`把儿子对应的`dp`值求出来
  另$$res1 = \sum dp(v)$$，求出第一种情况
  
*  第二种情况**抽路径**比较复杂，但我们可以`for x in path(u)`，遍历所有以`u`作为`lca`的路径
   不妨设路径上的点是$$x$$，需要知道$$x$$所有的儿子$$w$$的** dp 值之和**，可以考虑**线段树+dfs序**
   
   > 树形 dp 之前先用线段树维护 dp 值数组`dpv`，线段树维护**区间和**，`dfs(u)`的时候，对于点`x`
      它的 dp 值在递归的时候已经被求出来了
      执行**区间查询**$$[l(x), r(x)]$$，就知道$$x$$子树的 dp 值之和，当然要记得扣除$$dp(x)$$
      所以$$res2 += (\ [l_x, r_x] - dp_x \ )$$
   
   > `for 完 x 求出 res2`之后，另$$dp(u) = \max( dp(u), res1, res2 )$$，然后执行线段树**单点修改**
   >  $$l_u \to dp(u)$$
   
>  但很可惜**这样做是错的**，类似路径的权值和，参考[路径的修改和查询](https://www.ringalgo.com/article/10/)

错误的原因在于$$[l_x, r_x]$$还包含其他后代结点的 dp 值
![](/media/content_img/treepath-05.png)

难点实际上就是第二种情况**“抽路径”**，对于路径上的每一个点$$u$$
先根据第一种情况求出$$res1 = \sum dp_u$$，然后在$$res$$中把$$dp(u)$$给**抽掉**
对每个点再补上儿子的 dp 值之和 $$\sum dp_v$$

实际上，对于路径上的每个点$$u$$，在第二种情况的代价是$$cost(u) = -dp_u + \sum_v dp_v$$
这样，我们只要求出**一条路径上 cost 值之和**，就可以解决

> 求路径的权值和，想到了什么？**树链剖分 + 树状数组**

树状数组维护每个点的`cost`值
首先`dfs(u)`进行树形`dp`的时候，`for u 的所有儿子 v:    dfs(v)`，就可以把`v`的`dp`值挂载到`u`上
执行单点增加`add( l(u), dp(v) )`

对于$$u$$点挂载的每一段路径$$x \to u \to y$$，分成上升链和下降链，$$[x \to u), (u \to y]$$，`u = lca`单独考虑
树链剖分，划分成若干重链，每个重链都是`dfs序`上连续的一段，可以用树状数组区间查询，把`cost`值加起来等于$$res2$$
$$res2 \leftarrow res2 + ai$$，把这段路径的权值也算上，然后$$dp_u = \max(dp_u, res2)$$

这样就计算完成了$$u$$的`dp`值，别忘了把这个`dp`值**挂载**到树状数组相应的位置，维护`cost`值
`add( l(u), -dp(u) )`

这样就可以了

## 天天爱跑步（NOIP2016）
**[天天爱跑步 NOIP2016](https://www.luogu.com.cn/problem/P1600)**
**问题描述**
给定一个$$n$$个点的树，有$$m$$个玩家，每个玩家沿着路径$$(s_i \to t_i)$$走
每一名玩家都是从$$0$$秒开始，一秒走一条边

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

### 算法分析
![](/media/content_img/hld-noip2016-01.png)
![](/media/content_img/hld-noip2016-02.png)

这样基本就做完了，具体来说
先进行一遍 HLD，并进行**动态开点**
对于给定的路径$$(S, T)$$，拆成上升和下降，对于上升链，用主席树`tr1`维护，下降链用主席树`tr2`维护
对上升链，`[S --> lca]`中的每一段重链$$[lx, rx]$$，在`tr1[ dep(s) ]`中执行区间加$$1$$
对下降链，`[T --> lca]`中的每一段重链$$[lx, rx]$$，在`tr2[ dep(s)-2dep(lca)+MAX ]`区间加$$1$$
`LCA`重复计算了一次，在`tr1`或者`tr2`中扣除都可以，`tr1[ dep(s) ]`中单点修改，`l(lca)`处$$-1$$
>  `+MAX` 是为了避免负数

具体求解很简单，`for 每一个点 i`，然后上升链，下降链加起来
上升链，去`tr1[ w(i)+dep(i) ]`中单点查询`l(i)`的值
下降链，去`tr2[ w(i)-dep(i)+MAX ]`单点查询`l(i)`的值

### 算法实现
* 动态开点涉及到的点非常多，一般来说，只考虑**查询的时候会用到的那些点**
  可以在 HLD 之后，`for x = [1...n]`，把`root1[ w[x]+dep[x] ], root2[ w[x]-dep[x]+MAX ]`的线段树都开出来
  对每个点，从`root`到`l(x)`这个叶子结点上的点，都要被开出来
  ```bash
    void build(int p, int l, int r, int pos, const ll val) {
        if (l == r) {
            a[p].info = val, a[p].lazy = ID();
            a[p].l = a[p].r = 0;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) {
            if (!a[p].l) a[p].l = idx++;
            build(ls(p), l, mid, pos, val);
        }
        else {
            if (!a[p].r) a[p].r = idx++;
            build(rs(p), mid+1, r, pos, val);
        }
        pull(p);
    }
	// 每次递归一半，只开那一半的点
  ```
*  涉及到多棵线段树，用一个节点数组`a[MAXN*40]`来维护，`a`和根节点编号`idx`都要写成**全局变量**

* `push(p, l, r)`压标记也可以对应优化，**当儿子被开出来的时候**，才需要下传标记
  ```bash
    void push2(int p, int l, int r) {
        auto all_apply = [&](int p, ll f, int l, int r) -> void {
            a[p].info = mapping(f, a[p].info, l, r);
            a[p].lazy = composition(f, a[p].lazy);
        };
        int mid = (l + r) >> 1;
		
		// 重点在于这里，只需要对已经开出来的节点压标记即可
        if (a[p].l) all_apply(ls(p), a[p].lazy, l, mid);
        if (a[p].r) all_apply(rs(p), a[p].lazy, mid+1, r);
        a[p].lazy = ID();
    }
  ```
  
  对应的，在**区间修改**和**查询**的时候，先检查**对应的点有没有被开出来**
  如果没有开出来，直接`return`
  ```bash
  void modify(int p, int l, int r, ...) {
      if (p == 0) return;
	  // 其余代码省略
  }
  ll query(int p, int l, int r, ...) {
      if (p == 0) return 0LL;
  }
  ```
  
能这样做的原因是，对于每一条路径，它对答案有贡献，当且仅当上升链中，`dep[s] = w[x] + dep[x]`
下降链类似，那么`tr1( dep[s] ), tr2( w[x]+dep[x] )`应该是**同一棵**线段树
我们事先把需要查询的点，涉及到`x`，对应的线段树`tr1( w[x]+dep[x] )`**开出来**
如果`tr1( dep[s] ) = 0`，也就是说这个线段树还没被开出来，说明这条路径不会对点有影响，可忽略

##  树上路径2
**问题描述**
给定一个$$n$$个点的有根树，$$m$$条简单路径，每个路径有一个权值，并且这些路径都是一个点到它的祖先
要求选择一些路径，使得每个点至少在一条路径上，并且路径权值和最小

###  算法分析
这个问题和上个问题的区别在于，**一个点可能在多条路径上**，所以用之前的做法很难
如果在最高点考虑路径的话，很难转移，因为子树的每个点可能被覆盖$$\geqslant 1$$次
不能简单地考虑删除路径上的点，进行 dp 转移

分析一下如何定义状态
![](/media/content_img/treepath-06.png)

再考虑子树怎么和父亲合并
![](/media/content_img/treepath-07.png)

最后考虑**后缀最小值优化**
![](/media/content_img/treepath-08.png)

##  树上连通块
**问题描述**
给定一个$$n$$个节点的树，对于每个点，求出包含这个点的连通块的个数
答案对$$m$$取模，$$m$$不一定是质数
###  算法分析
考虑以$$u$$为根的子树
![](/media/content_img/treepath-09.png)

这样一看来，似乎**换根 dp** 可以解决这个问题
![](/media/content_img/treepath-10.png)

**用前缀积和后缀积优化**
![](/media/content_img/treepath-11.png)

###  算法实现
算法实现考虑**换根 dp**，实际上并不难写
![](/media/content_img/treepath-12.png)

记得特判根节点`ans[1] = dp[1]`，因为根节点没有`dp2`的值

```bash
void dfs(int u, int fa) {
    dp[u] = 1;
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        dp[u] = dp[u] * (dp[v] + 1) % MOD;
    }
}

vector<ll> dp2(maxn, 0), pre(maxn, 0), suf(maxn, 0);

void dfs2(int u, int fa) {
    int len = G[u].size();

pre[0] = 1LL;
    for (int i = 0; i < len; i++) {
        auto v = G[u][i];
        pre[i+1] = pre[i] * (dp[v] + 1) % MOD;
    }
    suf[len] = 1LL;
    for (int i = len-1; i >= 0; i--) {
        auto v = G[u][i];
        suf[i] = suf[i+1] * (dp[v] + 1) % MOD;
    }
    function<ll(int)> sibling = [&](int i) -> ll {
        return pre[i] * suf[i+1] % MOD;
    };

for (int i = 0; i < len; i++) {
        auto v = G[u][i];
        dp2[v] = sibling(i);
        if (u != 1) dp2[v] = dp2[v] * (dp2[u] + 1) % MOD;
    }

for (auto v : G[u]) {
        ans[v] = dp[v] * (dp2[v] + 1) % MOD;
        dfs2(v, u);
    }
}

int main() {
	dfs(1, 0), dfs2(1, 0);
	ans[1] = dp[1];
}
```

上一篇：树形动态规划（树形背包）下一篇：树形dp在算法竞赛中的应用

看完文章有啥想法

算法小站

树上动态规划（路径问题）