P1273 有线电视网
树上背包的变形
\[f_{u, j + k} = \max_{v \in son(u)} f_{u, j} + f_{v, k} - w_{u,v}
\]
这里写成 \(j + k\) 是为了和代码一致。
\(f_{u,j + k}\) 代表以 \(u\) 为根的子树中，选择了 \(j + k\) 个叶子结点的利润最大值。
\(w_{u, v}\) 代表 \(u\) 到 \(v\) 的边权。
然后就是很朴素的树上背包了，注意维护的是利润的最大值，有负数出现，需要初始化一下，详细见代码。
int n, m, w[N];
int sz[N], f[N][N], tmp[N], dep[N];
vector<pair<int, int>> e[N];
void dfs(int u)
{
if(u >= n - m + 1)
{
f[u][1] = w[u];
sz[u] = 1;
return;
}
sz[u] = 0;
for(auto [v, w] : e[u])
{
dfs(v);
for(int i = 0; i <= sz[u] + sz[v]; i++)
tmp[i] = f[u][i];
for(int i = 0; i <= sz[u]; i++)
for(int j = 0; j <= sz[v]; j++)
tmp[i + j] = max(tmp[i + j], f[u][i] + f[v][j] - w);
sz[u] += sz[v];
for(int i = sz[u]; i >= 0; i--)
f[u][i] = tmp[i];
// for(int i = sz[u]; i >= 0; i--)
// {
// cout<<"U: "<<u<<" V: "<<v<<" sz[u]: "<<i<<" f_u_sz: "<<f[u][i]<<'\n';
// }
}
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n - m; i++)
{
int k; cin>>k;
for(int j = 1; j <= k; j++)
{
int v, k; cin>>v>>k;
e[i].push_back({v, k});
}
}
for(int i = n - m + 1; i <= n; i++)
cin>>w[i];
for(int i = 1; i <= n; i++)
{
f[i][0] = 0;
for(int j = 1; j <= n; j++)
f[i][j] = -inf;
}
dfs(1);
for(int i = m; i >= 0; i--)
{
if(f[1][i] >= 0)
{
cout<<i<<'\n';
return;
}
}
return;
}