caioj 1114(树形DP)

caioj 1114
边权型树形DP,选$Q$条边等价于选$Q+1$个点。
那么边权转到点权上,做个普通树形背包即可

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
#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 = 310 + 5;
struct data {
int v, e_val;
}ed[MAXN * 2];
vector<int> G[MAXN];
int en, n, q, v_val[MAXN], dp[MAXN][MAXN];
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 dfs1(int u, int p) {
for (int i = 0; i < (int)G[u].size(); i++) {
int v = ed[G[u][i]].v, val = ed[G[u][i]].e_val;
if (v != p) {
v_val[v] = val;
dfs1(v, u);
}
}
}
void dfs2(int u, int p) {
for (int i = 0; i < (int)G[u].size(); i++) {
int v = ed[G[u][i]].v;
if (v != p) {
dfs2(v, u);
for (int j = q - 1; j >= 0; j--)
for (int k = 0; k <= j; k++) dp[u][j] = max(dp[u][j], dp[v][k] + dp[u][j - k]);
}
}
for (int j = q; j >= 0; j--)
if (j < 1) dp[u][j] = 0; else dp[u][j] = dp[u][j - 1] + v_val[u];
}
void clean() {
en = 0;
for (int i = 0; i <= n; i++) {
G[i].clear(), v_val[i] = 0;
for (int j = 0; j <= n; j++) dp[i][j] = 0;
}
}
void solve() {
clean();
q++;
for (int u, v, c, i = 1; i < n; i++) scanf("%d%d%d", &u, &v, &c), ins(u, v, c);
dfs1(1, 0);
dfs2(1, 0);
printf("%d\n", dp[1][q]);
}
int main() {
scanf("%d%d", &n, &q), solve();
return 0;
}

题目描述
有一棵苹果树,如果树枝有分叉,可以是分多叉,分叉数k>=0(就是说儿子的结点数大于等于0)这棵树共有N个结点(叶子点或者树枝分叉点),编号为1~N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量,求出最多能留住多少苹果。
输入格式:
输入第一行包含两个整数n,k(1<=k 输入接下来的n – 1行,每一行包含三个整数x,y,c,表示节点x和y之间有一条树枝。c表示这根树枝上苹果的数量。
输出格式:
输出一行,为最多可以保留的苹果数。

Input
6 2
1 3 1
1 4 10
1 6 21
2 3 20
3 5 20

Output
31

数据规模:
对于20%的数据,满足1 <= n <=15。
对于40%的数据,满足1 <= n <=100。
对于100%的数据,满足1 <= n <=310。

------ 本文结束 ------