1. #include <iostream>
    2. #include <vector>
    3. using namespace std;
    5. class Solver {
    6.     static const int MAXN = 100 + 5;
    7.     struct Edge {
    8.         int idx;
    9.         int v, w;
    10.         int last;
    11.     } edges[MAXN];
    13.     int dp[MAXN][MAXN] = {};
    15.     int cnt = 0, head[MAXN];
    16.     int N, V;
    17.     int root = 0;
    19.     void addEdge(int v, int w, int fa, int idx) {
    20.         if (fa == -1) fa = 0;
    21.         edges[cnt] = {idx, v, w, head[fa]};
    22.         head[fa] = cnt++;
    23.     }
    25.     void dfs(int idx) {
    26.         for (int e = head[idx]; e != -1; e = edges[e].last) {
    27.             Edge edge = edges[e];
    28.             dfs(edge.idx);
    29.             for (int i = V; i >= edge.v; i--) dp[edge.idx][i] = dp[edge.idx][i - edge.v] + edge.w;
    30.             for (int i = 0; i < edge.v; i++) dp[edge.idx][i] = 0;
    31.             for (int i = V; i >= 0; i--)
    32.                 for (int j = i; j >= 0; j--)
    33.                     dp[idx][i] = max(dp[idx][i], dp[idx][i - j] + dp[edge.idx][j]);
    34.         }
    35.     }
    37. public:
    38.     Solver() {
    39.         cin >> N >> V;
    40.         for (int i = 0; i <= N; i++) head[i] = -1;
    41.         int v[MAXN], w[MAXN], fa[MAXN];
    42.         for (int i = 1; i <= N; i++) {
    43.             cin >> v[i] >> w[i] >> fa[i];
    44.             if (fa[i] == -1) root = i;
    45.         }
    46.         for (int i = 1; i <= N; i++) addEdge(v[i], w[i], fa[i], i);
    48.         // for (int i = 0; i <= N; i++) {
    49.         //     cout << "root: " << i << endl;
    50.         //     for (int e = head[i]; e != -1; e = edges[e].last) {
    51.         //         cout << edges[e].v << " " << edges[e].w << endl;
    52.         //     }
    53.         //     cout << "------------" << endl;
    54.         // }
    56.         dfs(0);
    58.         cout << dp[0][V];
    59.     }
    60. };
    62. // 大概思路，看成分组背包问题，dp[i][j] 表示以 i 为根的子树，体积为 j 时的最大价值
    63. // 选的时候，可以把子节点所有的 j 看成一组，N 组里面，组内互斥
    64. /*
    65.     建好树以后，从根节点开始，递归算
    66.     每次先算完子节点的所有体积对应的最大价值，然后把每个子节点（直接子节点）看成一组，变成分组背包
    67.     注意一点，某一个节点选完以后，自己也要选，而且选不了自己的状态没有意义，要变 0
    68. */
    70. class Solver2 {
    71.     static const int MAXN= 100 + 5;
    73.     int v[MAXN], w[MAXN];
    74.     vector<int> g[MAXN];
    75.     int N, V;
    76.     int dp[MAXN][MAXN] = {};
    79.     // 更好理解的一种转移
    80.     // 一开始，默认所有 [v[x], V] 是选了 w[x]的
    81.     // 之后算完子节点后，进行枚举时，j 应该在 [V, v[x]] 里，因为 小于 v[x] 的 j 非法
    82.     // 而枚举组内物品时，组内物品体积需要在 [0, j - v[x]] 里，如果超出，则说明不能选 v[x]，不合法
    83.     void dfs(int idx) {
    84.         for (int i = v[idx]; i <= V; i++) dp[idx][i] = w[idx];
    85.         for (auto sub : g[idx]) {
    86.             dfs(sub);
    87.             for (int j = V; j >= v[idx]; j--)
    88.                 for (int k = 0; k <= j - v[idx]; k++)
    89.                     dp[idx][j] = max(dp[idx][j], dp[idx][j - k] + dp[sub][k]);
    90.         }
    91.     }
    93.     // 原版转移方式，子节点算完以后，在 [V - v[x], 0] 进行枚举，因为在这范围内枚举，才是能选 子节点的状态，而 [v[x], V] 会在子节点选完后，最后选
    94.     // 每个节点算完以后，因为只是转移完，还没有把自己加上去，所以得在最后加上根节点
    95.     // 加上根节点时，为什么从大到小，从小到大会使用已经加过根节点的状态
    96.     // 为什么要把 [0, v[x] - 1] 赋成 0，不这样做会导致从非法状态转移
    97.     void dfs2(int x) {
    98.         for (auto y : g[x]) {
    99.             dfs(y);
    100.             for (int j = V - v[x]; j >= 0; j--)
    101.                 for (int k = j; k >= 0; k--)
    102.                     dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[y][k]);
    103.         }
    104.         for (int i = V; i >= v[x]; i--) dp[x][i] = dp[x][i - v[x]] + w[x];
    105.         for (int i = 0; i < v[x]; i++) dp[x][i] = 0;
    106.     }
    108. public:
    109.     void f() {
    110.         cin >> N >> V;
    111.         int root, fa;
    112.         for (int i = 1; i <= N; i++) {
    113.             cin >> v[i] >> w[i] >> fa;
    114.             if (fa == -1) root = i;
    115.             else g[fa].push_back(i);
    116.         }
    117.         dfs2(root);
    118.         cout << dp[root][V] << endl;
    120.         for (int i = 0; i <= N; i++) {
    121.             for (int j = 0; j <= V; j++)
    122.                 cout << dp[i][j] << " ";
    123.             cout << endl;
    124.         }
    125.     }
    126. };
    128. int main() {
    129.     Solver2 s;
    130.     s.f();
    131. }