caioj 1107
二叉树树形DP，设$dp(u, a)$为$u$节点所为根的子树保留$a$条树枝的最优值
则 $dp(u, i) = max(dp(lc, i - j - 2) + dp(rc, j) | 1 \leq i \leq Q, 0 \leq j \leq i - 2)$(减二是因为要连接这两个子树所需要的代价)
初值$dp(u, 0) = 0$，最后的答案就很显然了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5;
struct data {
int v, val;
}ed[MAXN * 2];
vector<int> G[MAXN];
int n, q, dp[MAXN][MAXN], en;
void ins(int u, int v, int c) {
ed[en] = (data){v, c}, G[u].push_back(en++);
ed[en] = (data){u, c}, G[v].push_back(en++);
}
void dfs(int u, int p) {
int c1 = -1, c2 = -1, v1, v2, flag = true;
for (int i = 0; i < (int)G[u].size(); i++) {
int v = ed[G[u][i]].v, val = ed[G[u][i]].val;
if (v != p) {
flag = false;
if (c1 == -1) c1 = v, v1 = val;
else if (c2 == -1) c2 = v, v2 = val;
dfs(v, u);
}
}
if (!flag) for (int j = 1; j <= q; j++) {
dp[u][j] = max(dp[u][j], dp[c1][j - 1] + v1);
dp[u][j] = max(dp[u][j], dp[c2][j - 1] + v2);
for (int k = 0; k <= j - 2; k++) {
int l = j - 2;
dp[u][j] = max(dp[u][j], dp[c1][l - k] + dp[c2][k] + v1 + v2);
}
}
}
void clean() {
en = 0;
for (int i = 0; i <= n; i++) {
G[i].clear();
for (int j = 0; j <= n; j++) dp[i][j] = 0;
}
}
void solve() {
clean();
for (int u, v, c, i = 1; i < n; i++) scanf("%d%d%d", &u, &v, &c), ins(u, v, c);
dfs(1, 0);
printf("%d\n", dp[1][q]);
}
int main() {
scanf("%d%d", &n, &q), solve();
return 0;
}
/*
9 5
1 2 10
1 3 8
2 7 4
2 6 6
7 8 7
7 9 2
3 5 2
3 4 8
*/
题目描述
【问题描述】
有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）。这棵树共有N个结点（叶子点或者树枝分叉点），编号为1~N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
【输入格式】
第1行2个数，N和Q(1<=Q<= N,1<N<=100)。
N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。
每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。
【输出格式】
一个数，最多能留住的苹果的数量。
【样例】
输入：
5 2
1 3 1
1 4 10
2 3 20
3 5 20
输出：
21
