caioj 1114(树形DP)

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

#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。