树上背包练习
以第 $5$ 道题为例,展示一种可能的 模板
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5010,inf = 1e9 + 10;
vector<int> adj[N];
int F[N][N],G[N][N],f[N],g[N];
int main() {
cin.tie(0) -> sync_with_stdio(0);
int n,b;cin >> n >> b;
vector<int> c(n + 1),d(n + 1);
for(int i = 1,x;i <= n;i ++ ) {
cin >> c[i] >> d[i],d[i] = c[i] - d[i];
if(i > 1) {
cin >> x,adj[x].push_back(i);
}
}
for(int i = 1;i <= n;i ++ ) {
for(int j = 1;j <= n;j ++ )
F[i][j] = G[i][j] = inf;
}
vector<int> sz(n + 1),sum(n + 1);
for(int i = n;i >= 1;i -- ) {
F[i][1] = c[i],G[i][1] = d[i];
sz[i] = 1;
for(auto x : adj[i]) {
// 给临时数组赋 初始值
for(int j = 1;j <= sz[i] + sz[x];j ++ )
f[j] = inf,g[j] = inf;
// 使用已有的信息来推当前 加入考虑当前子树 后对于 dp 数组的影响
for(int j = 0;j <= sz[i];j ++ )
for(int z = 0;z <= sz[x];z ++ ) {
f[z + j] = min(f[z + j],min(inf,F[i][j] + F[x][z]));
if(j >= 1) g[z + j] = min(g[z + j],min(inf,G[i][j] + min(F[x][z],G[x][z])));
}
sz[i] += sz[x];
// 更新原先的 dp 数组
for(int j = 0;j <= sz[i];j ++ ) {
F[i][j] = f[j];
G[i][j] = g[j];
}
}
}
for(int i = n;i >= 0;i -- ) {
if(min(F[1][i],G[1][i]) <= b) {
cout << i << '\n';
break;
}
}
return 0;
}