一、题目描述
给定一棵含有 \(n\) 个结点的树，树根编号为 \(1\)，且树上的每条边有一个边权 \(w_j\)
要求我们只保留树中的 \(m\) 条边，使得 树根 所在的 连通块 的所有边 边权之和 最大
二、题目分析
想复习一下 背包\(DP\) 的同学，可以看看我之前写过的这篇 背包DP合集
这篇题解对于重复部分的知识不会再额外讲了QwQ
这题的题面其实就是 有依赖的背包 模型，不同的是把 物品价值 分给了 边 而不是 点
不过，对于一棵树来说，任意节点的入边（连向父节点的边） 都是 唯一 的
所以 边权 和 点权 在确定树的 根节点 以后，是可以视作一个东西的（入边价值 视作 该点价值）
常用的 有依赖的背包DP 集合划分方案有两个：
-
子物品体积集合划分 \(O(N×V×V)\) AcWing 10. 有依赖的背包问题【有依赖背包DP+子物品体积集合划分】
-
分组背包集合划分 \(O(N×2^k×V)\) AcWing 487. 金明的预算方案【有依赖背包DP+分组背包集合划分】
对于本题来说，分组背包集合划分 会超时，因此采用 体积集合划分方案
闫氏DP分析法
是有依赖背包问题的改编 https://www.acwing.com/solution/AcWing/content/8021/
树枝上苹果的数量可以理解成该边的权值
状态表示
\(f[u][j]\):表示所有以\(u\)为树根的子树中选，选\(j\)条边的最大价值
状态计算
每一棵子树看出一组背包，若需要选择该子树\(son\)，则根结点\(u\)到子树\(son\)的边一定用上，因此能用上的总边数一定减1，总共可以选择\(j\)条边时，当前子树\(son\)分配的最大边数是\(j - 1\)，对于任意一棵子树有
\(f[u][j] = max(f[u][j], f[u][j - 1 - k] + f[son][k]+ w[i])\)
其中： \(k∈[0,j−1]\)
\(Code\)
时间复杂度： \(O(N×V×V)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int M = N * 2;
int n; //表示树的节点数
int m; //表示要保留的树枝数量(背包容量)
int h[N], e[M], w[M], ne[M], idx;
int f[N][N];
//邻接表模板
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
//树形DP+无向图
void dfs(int u, int father) {
for (int i = h[u]; ~i; i = ne[i]) { //物品组
if (e[i] == father)continue; //不走回头路
dfs(e[i], u); //计算子分枝
//分组背包
for (int j = m; j; j--) //枚举u结点剩余体积
for (int k = 0; k < j; k++) //在这样的情况下，分给子树e[i]多大的体积？枚举体积预留一条连向父节点的边
//f[e[i]]-->son 子树
f[u][j] = max(f[u][j], f[u][j - 1 - k] + f[e[i]][k] + w[i]);
}
}
int main() {
//邻接表初始化
memset(h, -1, sizeof h);
cin >> n >> m;
//读入n-1条边
for (int i = 1; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
//建立无向图
add(a, b, c), add(b, a, c);
}
//有依赖的背包树形dp
dfs(1, -1);
//输出
printf("%d", f[1][m]);//以1号节点为根，边数不超过m（最大背包上限）的最大值
return 0;
}