算法

参考 福如东海大佬的解法

import java.util.*;
import java.io.*;

/*
多叉树的存储（左孩子，右兄弟）+ 记忆化递归
 */
class Main {

    static int N, M;
    static int[][] dp;
    //二叉树节点
    static int[] left, right;
    static int[] son;
    static int[] v, w;

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        N = in[0]; M = in[1];
        left = new int[N+1]; right = new int[N+1];
        v = new int[N+1]; w = new int[N+1];
        son = new int[N+1];
        dp = new int[N+1][M+1];
        for (int i = 0; i <= N; i++) {
            Arrays.fill(dp[i], -1);
        }
        int root = 0;
        for (int i = 1; i <= N; i++) {
            int[] t = read(br);
            v[i] = t[0]; w[i] = t[1];
            if (t[2] == -1) {
                root = i;
            } else {
                if (son[t[2]] == 0) {
                    left[t[2]] = i;
                } else {
                    right[son[t[2]]] = i;
                }
                son[t[2]] = i;
            }
        }
        out.println(dfs(root, M));
        out.flush();
    }

    //在i子树下，体积不超过j的情况下，能得到的最大收益
    //子树的选取不是孤立的，是可以一起选的，所以应该按照体积分配划分子树
    public static int dfs(int i, int j) {
        // i=0子树不存在
        if (i==0 || j < 0) return 0;
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        //不选当前节点，体积j全部分配给兄弟节点
        dp[i][j] = dfs(right[i], j);
        //当前节点必选，分给子节点k，兄弟节点j-v[i]-k
        for (int k = 0; k <= j-v[i]; k++) {
            dp[i][j] = Math.max(dp[i][j], dfs(left[i], k) + dfs(right[i], j-v[i]-k) + w[i]);
        }
        return dp[i][j];
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}