树上背包 - 洛谷保存站

树上背包，在合并俩子树时需要做 (max, +) 卷积，但这是 $O(m^2)$ 的，下面介绍一些规避 (max, +) 卷积的方法。核心思想是改变考虑 dp 的方式。
#### 以 dfs 序的角度考虑 dp
例题：$n$ 个点的一个有根树，点有点权，给定 $m$，对每个点 $x$，求出包含根以及 $x$ 的大小 $m$ 的点权和最大的连通块。  $n\le 5000$。  
这个正常 dp 不太好做（有人懂的话教教我 /kel），感觉只能暴力的 $O(n^3)$，无法通过。但是如果换个角度考虑就比较容易了。  
我们把树看成 dfs 序列，每个子树就是 dfs 序上的区间，共 $n$ 个，把连通块看成是删了一些子树后剩下的东西，那么问题就转化成：在 dfs 序上删一些区间，留下 $m$ 个点的最大权值和，然后要钦定留下点 $x$，这是经典问题，对前后缀分别 $dp$，设 $dp_{i,j}$ 表示前 $i$ 个数，留了 $j$ 个没删的最大权值和，转移要么留下 $i$，即 $dp_{i-1,j-1}+w_i$，要么删掉 $i$，枚举所有 $r_u=i$ 的区间 $u$，从 $dp_{l_u-1,j}$ 转移过来，由于区间总数为 $n$，因此这个 $dp$ 复杂度是 $O(n^2)$ 的，后缀同理。最后枚举 $x$ 即可得到答案。  
QOJ4815 $O(nk\log \frac{n}{k})$ /se。

#### 每次加入一个点的 dp
例题：树上最大权独立集，$n\le200,m\le50000$。  
给出如下暴力做法（伪代码），其中 `base` 是一个大小为 $m$ 的数组，表示树上最大权独立集的 dp 的初始状态，dfs 返回的是以 base 为初始状态的 dp 数组：
```
dfs(x, base)
    res = (base, base) // res[0] 表示选 x，res[1] 表示不选 x
    for y in son(x)
    	a = dfs(y, res[0])
        b = dfs(y, res[1])
        res[0] = a[1] // 选 x 只能不选 y
        res[1] = max{b[0], b[1]} // 不选 x，y 取较优者
    for i from w[x] to m
    	res[0][i] = res[0][i - w[x]] + v[x]
    return res
```
分析复杂度：$T(n)=2(T(n_1)+T(n_2)+\cdots+T(n_k))+O(m)$，最坏情况下是 $O(n^2m)$ 的。但一个优化技巧在于：第一个儿子传的 `res[0]` 和 `res[1]` 是一样的，所有事实上对第一个儿子，只需调用一次 dfs，另这个儿子是重儿子，这样 $T(n)=T(n_1)+2(T(n_2)+\cdots+T(n_k))+O(m)$，且 $n_1=\max_{i=1}^{k}n_i$，这样最坏情况也是 $O(n^{\log_2 3}m)$ 的。  
如果要对每个点算答案，考虑到只有当 base 是空时才能算，而重链上的 base 必然为空，因此对于新算法 $T'$，其只需对轻儿子调用新算法，对重儿子调用原先的算法，复杂度仍为 $O(n^{\log_2 3}m)$。  
相关题目：ABC 311 Ex Many Illumination Plans

正在渲染内容...