题面

大秦为你打开题目传送门

题目描述

有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）

这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树：

1
2
3
4
5
2   5
 \ / 
  3   4
   \ /
    1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

输入格式

第一行 $2$ 个整数 $N$ 和 $Q$，分别表示表示树的结点数，和要保留的树枝数量。

接下来 $N-1$ 行，每行 $3$ 个整数，描述一根树枝的信息：前 $2$ 个数是它连接的结点的编号，第 $3$ 个数是这根树枝上苹果的数量。

输出格式

一个数，最多能留住的苹果的数量。

样例 #1

样例输入 #1

1
2
3
4
5
5 2
1 3 1
1 4 10
2 3 20
3 5 20

样例输出 #1

1
21

提示

$1 \leqslant Q < N \leqslant 100$，每根树枝上的苹果 $\leqslant 3 \times 10^4$。

思路

既然要我们求最多能留住的苹果数量，我们不妨直接设 $dp[u][k]$ 表示这个点 $u$ 的子树中，保留 $k$ 个树枝的苹果最大值。

那么如何转移呢？

我们考虑 $u$ 连到 $v$ 的这个数值要不要剪掉，或者说是，$u$ 的儿子 $v$ 要不要。我们要考虑的是，如果 $v$ 不要了，那么他的那一整个子树，都会消失。所以说，我们要考虑的也可以变成，我当前的这个子树要保留 $j$ 个，然后 $v$ 的子树要保留 $k$ 个比较合理。

那么这个的转移方程也就不难想了。我们枚举一个 $j$ 枚举一个 $k$ 然后这个就是：

这个也好理解，不再讲述。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 int128;

namespace FastIO {
	template<typename Tp>
	inline void read(Tp &x) {
		char ch;
		int flag = 0;
		x = 0;
		while(!isdigit(ch = getchar())) if(ch == '-') flag = 1;
		while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch - '0'), ch = getchar();
		if(flag) x = -x;
	}
	template<typename Tp , typename ...  Args>
	inline void read(Tp &x, Args & ... x_) {
		read(x);
		read(x_ ... );
	}
};
using namespace FastIO;

const int N = 110;
const int M = 210;

struct Edge {
	int to, nt, wt;
	Edge() {}
	Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
};
class Graph {
private :
	Edge e[M];
	int hd[N], cnte;
public :
	inline void AddEdge(int u, int v, int w = 0) {
		e[++cnte] = Edge(v, hd[u], w);
		hd[u] = cnte;
	} 
	inline int head(int u) { return hd[u]; }
	inline int to(int u) { return e[u].to; }
	inline int nt(int u) { return e[u].nt; }
	inline int wt(int u) { return e[u].wt; }
};

int n, Q;
Graph G;

ll dp[N][N];
int sz[N];

inline void Input() {
	read(n, Q);
	int u, v, w;
	for(int i = 1; i < n; i++) {
		read(u, v, w);
//		cout << u << ' ' << v << ' ' << w << endl;
		G.AddEdge(u, v, w);
		G.AddEdge(v, u, w);
	}
//	cout << 1 << endl;
}

inline void Dfs(int u, int fa) {
//	cout << u << ' ';
	for(int i = G.head(u); i; i = G.nt(i)) {
		int v = G.to(i);
		if(v == fa) continue;
//		cout << v << ' ';
		Dfs(v, u);
		sz[u] += sz[v] + 1;
		for(int j = min(sz[u], Q); j > 0; j--) {
			for(int k = min(sz[v], j - 1); k >= 0; k--) {
				dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + G.wt(i));
			}
		}
	}
//	cout << endl;
}

inline void Work() {
	Dfs(1, 0);
	printf("%lld\n", dp[1][Q]);
}

int main() {
	int T = 1; 
//	read(T);
	while(T--) {
		Input();
		Work();
	}
	return 0;
}