题面
大秦为你打开题目传送门
题目描述
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树：
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式
第一行 $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 \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$ 然后这个就是：
$$
dp[u][j] = \max_{0\le k\lt j \le siz[u]}{dp[u][j - k - 1] + dp[v][k] + wt}
$$
这个也好理解，不再讲述。
代码
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);
G.AddEdge(u, v, w);
G.AddEdge(v, u, w);
}
}
inline void Dfs(int u, int fa) {
for(int i = G.head(u); i; i = G.nt(i)) {
int v = G.to(i);
if(v == fa) continue;
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));
}
}
}
}
inline void Work() {
Dfs(1, 0);
printf("%lld\n", dp[1][Q]);
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
