【学习笔记】树上背包的另类写法
XFrostKris
·
·
算法·理论
树上背包基础
树上背包模型：选择子节点那么父节点必须选择。
树上背包时可能原图不是树，可以建立虚拟节点 0 即可。
常见定义：定义 dp[u][i][j] 表示以 u 为根，前 i 个子节点限重为 j 的最优，并使用滚动数组。
变成 dp[u][j] = \max(dp[u][j], dp[v][k] + dp[u][j - k])，j 倒序枚举。
特殊解法
众所周知：u 节点的子树为 dfn 序在 [dfn[u], dfn[u] + siz[u] - 1] 范围内。
那么我们可以像 01 背包那样，不选择 i 就跳过其所有子树，直接考虑 dfn[i] + siz[i] 及其之后的元素。
我们建立虚拟源点 0，则其余全部节点的 dfn 范围为 [2, n + 1]，并且我们钦定 n + 2 节点为空。
定义 dp[i][j] 表示 dfn 为 [i, n + 2] 上的节点，总质量为 j，满足题意约束关系（先选父再选子）的最优结果，w[i] 为 i 的收益。
那么 $dp[i][j] = \max(dp[i + siz[i]][j], dp[i + 1][j - 1] + w[i])$。
枚举 $i$ 从最后一个不为空的到第一个。
举经典题目为例子：
[P2014 [CTSC1997] 选课](https://www.luogu.com.cn/problem/P2014)
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 305;
const int INF = 0x3f3f3f3f;
int n, m;
int f[N][N];
int dfn[N], rnk[N], siz[N];
int w[N];
int cnt = 0;
vector<int> e[N];
void dfs(int u, int fa) {
dfn[u] = ++cnt;
rnk[cnt] = u;
siz[u] = 1;
for (int v : e[u]) {
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
m++;
for (int i = 1, u; i <= n; i++) {
cin >> u >> w[i];
e[u].push_back(i);
e[i].push_back(u);
}
dfs(0, 0);
for (int i = n + 1; i; i--) {
for (int j = 1; j <= m; j++) {
f[i][j] = max(f[i + siz[rnk[i]]][j], f[i + 1][j - 1] + w[rnk[i]]);
}
}
cout << f[1][m];
return 0;
}
```
### 复杂度分析
本质上是对 dfn 序做 01 背包，每个节点只枚举一次容量，时间复杂度为 $O(n \cdot m)$，其中 $n$ 为节点数，$m$ 为背包容量；空间复杂度为 $O(n \cdot m)$（可优化至 $O(m)$）。