树形动态规划（树形背包）

[[ slider_text ]]

[[ item.c ]]

树形动态规划（树形背包）

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

dp 树上问题 树形dp

## 树上背包（权值和最大）
**问题描述**
给定一个$$n$$个点的有根树，每个点有点权$$v_i$$，权值可能是负数
对于每个点，求在它的子树中选择一个包含这个点的连通块，使得权值和最大

### 算法分析
令$$dp(i)$$表示$$i$$这个点的子树（包括$$i$$）的连通块的最大权值和
那么对于$$u$$，以及$$u$$的所有儿子$$v_i$$，$$w$$表示点权，我们有

$$\displaystyle dp(u) = w(u) + \sum_i  \max \left(0, dp(v_i) \right)$$

##  树上背包，有条件
**问题描述**
给定一个$$n$$个点的有根树，每个点有点权$$v_i$$，权值可能是负数
回答$$q$$个询问，在$$u$$的子树中，选择一个大小恰好为$$m$$的，包含$$u$$的连通块，求最大权值和
### 算法分析
> 和之前的问题比，区别在哪里？

加了一个限制，一个关于`size`的限制，$$dp(i, j)$$表示选包含$$i$$这个点的连通块，并且选择了$$j$$个点的最大权值和
![](/media/content_img/treedp-1.png)
可以先写一个暴力的做法，遍历所有的儿子，然后再遍历儿子的`size`，这样复杂度好像是$$O(n^3)$$的

但类似 DSU On Tree，实际上`合并 u 的儿子`的代价，可能不会那么大（类似启发式合并）

> 时间复杂度到底是多少？

![](/media/content_img/treedp-2.png)
一个点对发生合并需要$$1$$的代价，有$$O(n^2)$$的点对，代价是$$O(n^2)$$的

### 算法实现
```bash
dfs(u):
	for u 所有的儿子 v：
		dfs(v)
		用临时数组 tmp 来统计合并信息
		for i = [1...sz(u)], for j = [1...sz(v)]:
			tmp(i+j) = max(tmp(i+j), dp(u, i) + dp(v, j))
	
		sz(u) += sz(v)
		dp(u)[...] = tmp[...]
		
// 注意这里要往右平移
// 这里应该包含 u 这个点，才能达到`size = i`的大小
for i = sz(u) -> 1:		dp(u, i) = dp(u, i-1) + w(u)
```
注意到子树中还包含`u`点，所以应该是`dp(u, i)`对应`dp(u, i+1)`，同时还需要在子树中把`u`这个点权值算上
也就是说把`dp(u)[...]`数组往右平移一位，然后再加上`w(u)`

可以这么理解，之前的计算将`u`当成是**虚拟的点**，所以`dp(u, i)`，实际上它的`size`只有`i-1`
所以`dp(u, i) = dp(u, i-1) + w(u)`
**相当于 i 这个维度向右平移**

## 树上背包，优化
**问题描述**
给定一个$$n$$个点的有根树，每个点有点权$$v_i$$，权值可能是负数
回答$$q$$个询问，在$$u$$的子树中，选择一个大小恰好为$$m$$的，包含$$u$$的连通块，求最大权值和
这里$$n = 50000$$，$$O(n^2)$$的做法会被卡，但$$m$$范围很小，只有$$m \leqslant 100$$

### 算法分析
分析方法和之前类似，只不过这里$$dp(u, j)$$，$$j$$这个维度只需要$$\leqslant m$$就可以
复杂度是$$O(nm)$$的
合并子树$$i, j$$的代价是`min(size(i), m) * min(size(j), m)`，`for 子树的时候需要 <= min(size, m)`

> 直接`for`到`m`是不对的，因为实际上越接近叶子结点，它的子树大小是越小的，会趋于`1`

## 树上背包，带权值和容量
**问题描述**
给定一个$$n$$个点的有根树，每个点给定权值$$a_i$$，重量$$w_i$$
现在要求，选择一个重量和恰为$$m$$的，包含根的连通块，最大的权值和

### 算法分析
>  和之前的问题区别在哪？

这个问题是包含根的连通块，一个点被选，那么$$u \to root$$路径上的点也要被选
$$dp(i, j)$$表示从$$i$$这个点的子树中，选出了一个连通快，包含$$i$$，并且重量恰好等于$$j$$的最大权值和
注意到每个物品都有重量，所以需要`for`的儿子个数可能很少，但是状态是$$O(m)$$级别的

> 举个例子，可能只有$$3$$个结点，但是重量是$$\left<1, 2, 9 \right>$$，这个时候需要遍历$$[1\to 10]$$
> $$O(m)$$的状态是可以取到的，复杂度会退化到$$O(m^2)$$

> 那么，怎么优化呢？

注意到很重要的一点，之前树上独立集问题，考虑的方案是$$i$$这个点选还是不选
如果我们从这个角度来看，$$i$$如果不选进来，那么$$i$$**的子树也都不会被选**，遍历的时候跳过子树
是不是就能够优化一部分时间复杂度？

**跳过子树**，想到了** dfs 序**
![](/media/content_img/treedp-3.png)

dfs 序能够帮我们完成**跨分支跳跃**这一件事情，如果$$i$$的子树不选，我们需要对$$i$$跨分支跳跃
dfs 序会用$$r_x$$来标记结点$$x$$的相邻分支的时间戳，考虑 dfs 序的时候，若不选$$x$$，直接$$x \to r_x$$

dp的定义如上图所示，这样就可以写转移方程了

$$dp(i, j) = \max\left( dp(r_i, j), dp(i+1, j-w_i) + a_i \right)$$

其中$$dp(r_i, j)$$的转移，表示不选$$i$$这个点，考虑从$$r_i$$的分支转移过来
$$dp(i+1, j-w_i) + a_i$$ 表示正常选$$i$$这个点的转移

> 注意的是，这里的 $$dp(i,j)$$ 我们只要求考虑$$S = [i\cdots n]$$这一段，硬性要求是选的点集的重量和$$\leqslant j$$
> 还有一个硬性要求，就是如果一个点选了，那么$$\in S$$的所有祖先也要选
> 至于$$i$$这个点，最优解中，可能选了，也可能不选，没有硬性要求

经上面的分析，倒着遍历$$i$$，考虑$$i$$这个点选或者不选，就是**经典背包问题**

> 算法实现的时候注意几点

* `dfs`序中的$$i$$，要注意对应到树中的**真实结点**$$u$$，从而加上权值$$a_u$$

*  问题要求恰好$$k$$个，可以把初始状态设置成$$-\infty$$（因为 dp 方程是取$$\max$$）
   初始状态是一个点都没有选，也就是说`dp(n+1)[...]`，只有`dp(n+1, 0) = 0`是合法的，`n+1`处`size = 0`才合法
   其他`dp(n+1)[1...m] = -inf`，均不合法

上一篇：双连通分量的一些例子下一篇：树上动态规划（路径问题）

看完文章有啥想法

算法小站

树形动态规划（树形背包）