思路和背包九讲里面的泛化物品相似，假设每个节点有n个子，对于每个子，可以选择选和不选，如果不选，这个子的费用则为0，如果选的话，要算出来1-V这些费用的最优解。同理，要算出每个子的0-V的最优解。那么这个问题就转换成了分组背包问题，每个子是每个组，每个组里有C个物品，费用分别为（0-V），然后DP求解

每个节点在算的时候会有重复，所以拿来一个memo来记忆就行了。由于这道题的索引是根据依赖树来的，所以memo记录的时候不是从小到大的。转换为非递归方法会有一些困难，所以就用记忆化搜索了

考虑到填满memo，加上每一层的DP是O(NCC), 那么最终的复杂度应该是O(N^2*C^3), 感觉有点高，欢迎别人指出正确的复杂度

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        // Read N and C
        String[] s = in.readLine().split(" ");
        int N = Integer.parseInt(s[0]); // unique group count
        int C = Integer.parseInt(s[1]); // knapsack capacity

        int[] ss = new int[N];
        int[] vs = new int[N];

        List<Integer>[] tree = new List[N+1]; // index is item's index + 1, tree[0] is root, value is List of children item index
        Arrays.setAll(tree, e -> new ArrayList<>());

        // Read size and value for each item
        for (int i=0; i<N; i++) {
            s = in.readLine().split(" ");
            ss[i] = Integer.parseInt(s[0]);
            vs[i] = Integer.parseInt(s[1]);
            int di = Integer.parseInt(s[2]);
            tree[di < 0 ? 0 : di].add(i);
        }

        // Output result
        System.out.println(knapsackDPRecursive(N, C, ss, vs, tree));
    }

    private static int knapsackDPRecursive(int N, int C, int[] ss, int[] vs, List<Integer>[] tree) {
        int[][] memo = new int[N+1][C+1];
        for (int i=0; i<N+1; i++) {
            for (int j=0; j<C+1; j++) {
                memo[i][j] = -1;
            }
        }
        return knapsackDPRecursive(C, ss, vs, 0, tree, memo);
    }

    // the max value after chosen root
    private static int knapsackDPRecursive(int C, int[] ss, int[] vs, int root, List<Integer>[] tree, int[][] memo) {
        if (memo != null && memo[root][C] >= 0) {
            return memo[root][C];
        }

        List<Integer> children = tree[root];
        int N = children.size();
        int[][] values = new int[N][C+1]; // the max value for each child and each capacity
        for (int i=0; i<N; i++) {
            int s = ss[children.get(i)], v = vs[children.get(i)];
            for (int j=s; j<=C; j++) {
                values[i][j] = knapsackDPRecursive(j-s, ss, vs, children.get(i)+1, tree, memo) + v;
            }
        }

        // Now it can think of there are N groups of items and each group there are C items to choose from
        // the jth item within ith group has size of j and value of values[i][j]
        // So can solve using group-knapsack way
        int[] dp = new int[C+1];
        for (int i=0; i<N; i++) {
            for (int j=C; j>=1; j--) {
                for (int k=1; k<=j; k++) { // each group got C items
                    dp[j] = Math.max(dp[j], dp[j-k]+values[i][k]);
                }
            }
        }

        memo[root][C] = dp[C];

        return dp[C];
    }
}