$$\color{Red}{二叉苹果树有依赖的分组背包 步骤详解}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。

这棵树共 N 个节点，编号为 1 至 N，树根编号一定为 1。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。

一棵苹果树的树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的
树枝数量，求最多能留住多少苹果。

这里的保留是指最终与1号点连通。

输入格式

第一行包含两个整数 N 和 Q，分别表示树的节点数以及要保留的树枝数量。

接下来 N−1 行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。

输出格式
输出仅一行，表示最多能留住的苹果的数量。

数据范围

1≤Q<N≤100

N≠1

每根树枝上苹果不超过 30000 个。

输入样例：

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

输出样例：

21

思考

有依赖的背包问题

一个很明显的基本准则：当我们选择一个子节点，它的父节点和所有的祖先路径的点都需要选择

这题和有依赖的背包问题的不同点在于，之前是点存储的价值，而这道题是边权为价值。
我们类似之前有依赖的背包问题，设定划分动态规划：f[i][j]，之前是设定以根节点为i，可以分配到子树下体积为j。这道题我们选择划分节点下的子树的边数为j，而苹果的数量为价值。

那么我们按分组背包的思路去动态规划的思想，枚举决策的时候应该是：

一旦选择了一个子节点，划分的时候，根节点应该是f[x][j - 1 - k] + f[son][k] + w[i]，枚举给子节点分配k,而根节点多减一个1是因为我们认定必然还会选择根节点x到son这条边，因此加上了他们之间的边权。

java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 110, n, m, idx;
    static int[] e = new int[2 * N];
    static int[] ne = new int[2 * N];
    static int[] w = new int[2 * N];
    static int[] h = new int[N];
    static int[][] f = new int[N][N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }

    static void dfs(int x, int father) {
        for (int i = h[x]; i != -1; i=ne[i]) {
            int son = e[i];
            if (son == father) continue;
            dfs(son, x);
            //循环体积
            for (int j = m; j >= 0; j--) {
                //循环决策
                for (int k = 0; k < j; k++) {
                    f[x][j] = Math.max(f[x][j], f[x][j - 1 - k] + f[son][k] + w[i]);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Arrays.fill(h, -1);
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 0; i < n - 1; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a, b, c);
            add(b, a, c);
        }
        dfs(1, -1);
        System.out.println(f[1][m]);
    }
}