算法
(树上分组背包)
记 dp[v][j]
表示以点 $v$ 为根的子树给 $j$ 个用户提供服务,能获得的最大收益
对于以 $v$ 为根的子树,$u$ 是它的子节点,我们可以让点 $u$ 服务 $k$ 个用户,其他用户交给 $u$ 前面的儿子去服务,则问题转化为分组背包
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::vector;
using std::function;
using P = std::pair<int, int>;
const int MX = 3005;
int w[MX];
vector<P> g[MX];
int dp[MX][MX];
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n, m;
cin >> n >> m;
rep(i, n-m) {
int k;
cin >> k;
rep(j, k) {
int a, c;
cin >> a >> c;
g[i].emplace_back(a, c);
}
}
for (int i = n-m+1; i <= n; ++i) cin >> w[i];
memset(dp, ~0x3f, sizeof dp);
// 对于任何点,不提供服务,收入为 0
rep(i, n) dp[i][0] = 0;
// 以 v 为根的子树的叶子数量
function<int(int)> dfs = [&](int v) -> int {
if (v >= n-m+1) {
dp[v][1] = w[v];
return 1;
}
int totleaf = 0;
for (auto& [u, c] : g[v]) {
int leaf = dfs(u);
totleaf += leaf;
// 类似01背包,倒着循环可以滚动数组优化一个维度
for (int j = totleaf; j > 0; --j) {
for (int k = 1; k <= min(j, leaf); ++k) {
chmax(dp[v][j], dp[v][j-k] + dp[u][k] - c);
}
}
}
return totleaf;
};
dfs(1);
int ans = 0;
for (int i = m; i >= 1; --i) {
if (dp[1][i] >= 0) {
ans = i;
break;
}
}
cout << ans << '\n';
return 0;
}