题目描述
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为 1∼N，树根编号一定是 1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 个树枝的树：
代码语言：javascript复制2 5
/
3 4
/
1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式
第一行 2 个整数 N 和 Q，分别表示表示树的结点数，和要保留的树枝数量。
接下来 N−1 行，每行 3 个整数，描述一根树枝的信息：前 2 个数是它连接的结点的编号，第 3 个数是这根树枝上苹果的数量。
输出格式
一个数，最多能留住的苹果的数量。
输入输出样例
输入 #1复制
代码语言：javascript复制5 2
1 3 1
1 4 10
2 3 20
3 5 20
输出 #1复制
代码语言：javascript复制21
说明/提示
1⩽Q<N⩽100，每根树枝上的苹果 。
题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P2015
- 参考题解：https://www.luogu.com.cn/problem/P2015
- 标签：
OI、动态规划、树形DP
正解
- 树形dp没得跑，其中表示根节点为u的子树上保留了j条边所能得到的苹果的最大数目
- 转移方程：, )
- 代码里放了-1的原因，记得倒序枚举
代码
代码语言：javascript复制// 题目: 二叉苹果树
// 链接: https://www.luogu.com.cn/problem/P2015
// 难度: 普及 /提高
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
struct node {
int v, to, next;
} g[105];
vector<int> head(105, -1);
int cnt = 0, n, m, dp[105][105], size[105];
void add(int u, int v, int w) {
g[cnt].v = w;
g[cnt].to = v;
g[cnt].next = head[u];
head[u] = cnt;
cnt;
}
void dfs(int u, int father) {
for (int i = head[u]; ~i; i = g[i].next) {
int v = g[i].to;
if (v == father) {
continue;
}
dfs(v, u);
size[u] = size[v] 1;
for (int j = min(size[u], m); j > 0; --j) {
for (int k = min(size[v], j - 1); k >= 0; --k) {
// 要保留某条边那么根节点到这条边的所有边都要保留，所以-1
dp[u][j] = max(dp[u][j], dp[u][j - k - 1] dp[v][k] g[i].v);
}
}
}
}
void best_coder() {
cin >> n >> m;
for (int i = 1; i < n; i) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dfs(1, -1);
cout << dp[1][m];
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
return 0;
}
