算法分析

树形dp + 分组背包问题

是有依赖背包问题的改编https://www.acwing.com/solution/AcWing/content/8021/

树枝上苹果的数量可以理解成该边的权值

状态表示

• f[u][j]:表示所有以u为树根的子树中选，选j条边的最大价值

状态计算

• 每一棵子树看出一组背包，若需要选择该子树son，则根结点u到子树son的边一定用上，因此能用上的总边数一定减1，总共可以选择j条边时，当前子树son分配的最大边数是j - 1，对于任意一棵子树有

• f[u][j] = Math.max(f[u][j], f[u][j - 1 - k] + f[son][k]+ w[i])

时间复杂度

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main{
    static int N = 110;
    static int M = N * 2;
    static int n;
    static int m;
    static int[][] f = new int[N][N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int[] v = new int[M];
    static int idx = 0;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    static void dfs(int u ,int father)
    {
        for(int i = h[u];i != -1;i = ne[i]) // 循环组
        {
            int son = e[i];
            if(son == father) continue;
            dfs(son,u);
            for(int j = m;j >= 0;j --)  // 循环体积
            {
                for(int k = 0;k + 1<= j;k ++)  //循环决策
                    f[u][j] = Math.max(f[u][j], f[u][j - 1 - k] + f[son][k]+ w[i]);
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        Arrays.fill(h, -1);
        for(int i = 1;i <= n - 1;i ++)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            add(a,b,c);
            add(b,a,c);
        }

        dfs(1,-1);

        System.out.println(f[1][m]);

    }
}