#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 110; int n, m; int v[N], w[N]; int h[N], e[N], ne[N], idx; int f[N][N]; //f[i,j]表示所有从以i为根的子树中选,且总体积不超过j的方案 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void dfs(int u) { for(int i=h[u]; ~i; i=ne[i]) {//遍历u号点的所有子树 物品组 int son=e[i]; dfs(e[i]); //分组背包 for(int j=m-v[u]; j>=0; j--)//体积 for(int k=0; k<=j; k++)//循环决策,选哪个 当前用多少体积 //按体积划分 f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]); } //把点u加进去 for (int i = m; i >= v[u]; i -- ) f[u][i] = f[u][i - v[u]] + w[u]; //清空剩余的部分 放不进去的情况 for (int i = 0; i < v[u]; i ++ ) f[u][i] = 0; } int main() { cin >> n >> m; memset(h, -1, sizeof h); int root;//找根节点 for (int i = 1; i <= n; i ++ ) { int p; cin >> v[i] >> w[i] >> p; if (p == -1) root = i;//说明为根节点 else add(p, i);//依赖p号点,那就建一条p指向i的边 } dfs(root);//从根节点开始递归操作 cout << f[root][m] << endl;//表示考虑整课树的情况下,体积不超过m,最大价值是多少 return 0; }