1 题意
一棵以
原题中
不能直接挑最大的
2 边权转点权
沿用旧文的处理方法:将每条边的权值转移到它的孩子节点上。记转移后的点权为
连通的树中,边数比点数少
转换后,不能只选择后代而不选择它的祖先。否则既不连通,也会把尚未接通的父边权计入答案。
3 状态定义
定义
另外规定
初始只处理
其他状态为
4 分配名额
如果
这里必须检查
不同孩子如何分配名额,会影响最终收益。这就是树形背包:不再只给每个孩子取一个最优值,而是保留各个选择数量下的最优值,再枚举数量分配。
5 逐个合并
代码不必专门存左右孩子,可以将孩子逐个合并。这种写法也适用于孩子数量不限的树。
合并孩子
枚举时要求
每个孩子都用一份清空后的 next 数组接收结果,合并完成再覆盖
用
sz[u] 要在合并完成后增加,不能提前把当前孩子算入旧状态的规模。
6 手算示例
图中的树包含边
| 子树根 | ||||
|---|---|---|---|---|
| 2 | 0 | 20 | ||
| 5 | 0 | 20 | ||
| 3 | 0 | 1 | 21 | 41 |
| 4 | 0 | 10 | ||
| 1 | 0 | 0 | 10 | 21 |
根选择
- 全部分给节点
的子树,得到 。 - 两棵孩子子树各分一个,得到
。
所以答案为
虽然
7 正确性
考虑一次孩子合并。任意合法的非空选择,限制在旧部分和当前孩子子树后,分别得到大小为
反过来,任意两个满足条件的子方案,都能通过父子边接成一个合法连通方案,数量和收益分别相加。按选择总数取最大值,就得到合并后的最优状态。
逐个合并全部孩子后,
8 代码实现
dfs(u, fa, value) 中的 value 是父边转移到
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
const int NEG = -1000000000;
struct Edge {
int to, w;
};
vector<Edge> g[maxn];
int f[maxn][maxn], sz[maxn];
int n, q, K;
void dfs(int u, int fa, int value) {
for (int j = 0; j <= K; ++j) f[u][j] = NEG;
f[u][0] = 0; // 整棵子树都不取
f[u][1] = value; // 只取 u;value 是父边转移到 u 上的点权
sz[u] = 1;
int next[maxn];
for (auto [v, w] : g[u]) {
if (v == fa) continue;
dfs(v, u, w);
fill(next, next + K + 1, NEG);
// a 个点来自 u 和之前合并的孩子,必须包含 u。
for (int a = 1; a <= min(sz[u], K); ++a) {
if (f[u][a] == NEG) continue;
// b=0 表示不取当前孩子子树;b>0 时必须包含 v。
for (int b = 0; b <= min(sz[v], K - a); ++b) {
if (f[v][b] == NEG) continue;
next[a + b] = max(next[a + b], f[u][a] + f[v][b]);
}
}
for (int j = 1; j <= K; ++j) f[u][j] = next[j];
sz[u] += sz[v]; // 合并完成后再扩大已处理部分的规模
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
K = q + 1; // 保留 q 条边,等价于保留包含根的 q+1 个点
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0, 0); // 根没有父边,转移后的点权为 0
cout << f[1][K] << '\n';
return 0;
}
按每次合并枚举两个数量,可先得到时间上界
苹果总数不超过 int 即可。代码在相加前检查不可行状态。
9 相关题解
暂无相关题解