有依赖的背包问题（树形dp）

#include<iostream>
#include<vector>
using namespace std;
const   int N=110;
vector<int>g[N];
int root;
int v[N],w[N];
int f[N][N];   //指以i为根节点且包括i，总共分配最多j个容量的方案的最大值 
    int n,m;
void dfs(int u)
{
   
    for(int i=v[u];i<=m;i++)
    f[u][i]=w[u];
    for(int i=0;i<g[u].size();i++)
   {
   
       dfs(g[u][i]);           //把每个子树看成一个组，用分组背包模型。
     for(int j=m;j>=v[u];j--)       // 01背包要倒着枚举
     for(int k=0;k<=j-v[u];k++)   //枚举给子树分配的体积
     f[u][j]=max(f[u][j],f[u][j-k]+f[g[u][i]][k]);
   }
} 
int main()
{
   

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
   
      int   p;
      cin>>v[i]>>w[i]>>p;
      if(p==-1)
      root=i;
      else
      g[p].push_back(i);
    }
    dfs(root);
    cout<<f[root][m]<<endl;
}