【题目来源】
洛谷：P2015 二叉苹果树 - 洛谷
【题目描述】
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有 \(N\) 个结点（叶子点或者树枝分叉点），编号为 \(1∼N\)，树根编号一定是 \(1\)。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 \(4\) 个树枝的树：
2 5\ / 3 4\ /1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
【输入】
第一行 \(2\) 个整数 \(N\) 和 \(Q\)，分别表示表示树的结点数，和要保留的树枝数量。
接下来 \(N−1\) 行，每行 \(3\) 个整数，描述一根树枝的信息：前 \(2\) 个数是它连接的结点的编号，第 \(3\) 个数是这根树枝上苹果的数量。
【输出】
一个数，最多能留住的苹果的数量。
【输入样例】
5 2
1 3 1
1 4 10
2 3 20
3 5 20
【输出样例】
21
【算法标签】
《洛谷 P2015 二叉苹果树》 #动态规划DP# #树形数据结构# #树形DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 205; // 定义常量 N，表示最大节点数
int n, m; // n 表示节点数，m 表示选择的边数
int f[N][N], siz[N]; // f[u][k] 表示以 u 为根的子树中选择 k 条边的最大权值，siz[u] 表示以 u 为根的子树的大小
int h[N], e[N], ne[N], w[N], idx; // 邻接表存储图，h[u] 表示节点 u 的第一条边的索引，e[idx] 表示边的终点，ne[idx] 表示下一条边的索引，w[idx] 表示边的权值，idx 是边的计数器// 添加边到邻接表
void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; // 将边 (a, b) 添加到邻接表中，权值为 c
}// 深度优先搜索函数
void dfs(int u, int fa)
{for (int i = h[u]; i != -1; i = ne[i]) // 遍历节点 u 的所有邻接边{int j = e[i]; // j 是当前边的终点if (j == fa) continue; // 如果 j 是父节点，跳过dfs(j, u); // 递归遍历子树siz[u] += siz[j] + 1; // 更新以 u 为根的子树的大小// 动态规划转移，避免变量名冲突，将内层循环变量改为 kkfor (int kk = min(m, siz[u]); kk >= 0; kk--) // 遍历可能的边数 kkfor (int k = 0; k <= min(kk - 1, siz[j]); k++) // 遍历子树 j 中选择的边数 kf[u][kk] = max(f[u][kk], f[u][kk - k - 1] + f[j][k] + w[i]); // 更新 f[u][kk] 的值}
}int main()
{cin >> n >> m; // 输入节点数 n 和选择的边数 mmemset(h, -1, sizeof h); // 初始化邻接表头数组 hmemset(siz, 0, sizeof siz); // 初始化 siz 数组memset(f, 0, sizeof f); // 初始化 f 数组for (int i = 1; i < n; i++) // 输入 n-1 条边{int u, v, w;cin >> u >> v >> w; // 输入边的两个端点和权值add(u, v, w), add(v, u, w); // 将边 (u, v) 和 (v, u) 添加到邻接表中}dfs(1, 0); // 从根节点 1 开始深度优先搜索cout << f[1][m] << endl; // 输出以 1 为根的子树中选择 m 条边的最大权值return 0;
}
【运行结果】
5 2
1 3 1
1 4 10
2 3 20
3 5 20
21