题目
题目描述
有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共N个节点，标号1至N，树根编号一定为1。
我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。
输入描述
第一行两个数N和Q，N表示树的节点数，Q表示要保留的树枝数量。
接下来N-1行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。
输出描述
输出仅一行，表示最多能留住的苹果的数量。
示例1
输入
5 2
1 3 1
1 4 10
2 3 20
3 5 20
输出
21
备注
对于 \(100 \%\) 的数据，\(1 \le Q \le N \le 100,N \neq1\) 每根树枝上苹果不超过30000个。
题解
知识点：树形dp。
这是一道经典的树上背包，因为每个点所在子树都可以分配一个边数（体积），并在这种情况下得到最值，而每次选的时候每个子节点都是不确定边数（体积）的，因此是个分组背包，每组都有不同的体积对应的贡献可选，只能选一个。
设 \(dp[u][i]\) 表示以 \(u\) 为根节点的子树，有 \(i\) 条边（包括子树头顶上连着父节点的边）的时候的最大苹果数。有转移方程：
\[dp[u][i] = \max (dp[u][i],dp[u][i-j] + dp[v][j-1]+w) \]表示为从子节点 \(v\) 的子树选取 \(j-1\) 条边，而子树需要头顶上还需要一条边连着父节点，因此原来的 \(u\) 的子树需要有 \(i-j\) 条边，再算上这条边的贡献 \(w\) ，加在一起就是当前情况的价值。注意这是一个滚动数组，总边数 \(i \in [1,q]\) 需要倒序遍历（\(i = 0\) 是 \(0\)），而选的 \(j \in [1,i]\) 相当于一个组中不同物品体积，正序即可。
由于这个背包都是正整数贡献的，默认 \(0\) 即可，放空气肯定没放物品贡献多。
时间复杂度 \(O(nq^2)\)
空间复杂度 \(O(nq)\)
代码
#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<pair<int, int>> g[107];
int dp[107][107];
void dfs(int u, int fa) {
for (auto [v, w] : g[u]) {
if (v == fa) continue;
dfs(v, u);
for (int i = q;i >= 1;i--) {///体积,在u点滚动一个分组背包,i表示共多少边
for (int j = 1;j <= i;j++)///每个子树都可以选j-1条边,加上子树链接根节点共j条（j=0即背包前，已包含）
dp[u][i] = max(dp[u][i], dp[u][i - j] + dp[v][j - 1] + w);
}
}
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
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);
cout << dp[1][q] << '\n';
return 0;
}