原題鏈接
關(guān)鍵：當(dāng)遞歸處理u結(jié)點的子樹返回時，進(jìn)行分組背包的決策，各個子樹中的結(jié)點可能非常多私痹，可能有100多個結(jié)點凰萨，因此，如果以方案來劃分最多有2^100種類別丝格，所以要改用體積來劃分
從j表示當(dāng)前除去v[u]的體積，j從[ m - v [u] , 0 ]的體積中枚舉（類別）,k選取體積是0，是1......是j（選一個）——>轉(zhuǎn)化為分組背包問題
轉(zhuǎn)移方程為：dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k])
物品組選完以后努咐，再將u結(jié)點如，此時需要枚舉背包剩余體積
1.對于j>=v[u]&&j<=m的體積殴胧，可以裝入u結(jié)點渗稍，更新相應(yīng)的dp數(shù)組
2.對于j<v[u]的體積佩迟，無法裝入u結(jié)點，因此以u為根節(jié)點的子樹不存在竿屹，dp[u][j]=0;
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=110;
int n,m;
int h[N],e[N],idx,ne[N];
int v[N],w[N];
int dp[N][N];//表示在所有以u為根的子樹中選报强，且總體積不超過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])//枚舉物品組
{
int son=e[i];
dfs(e[i]);
//分組背包的過程,對于這一組子樹內(nèi)部以體積劃分
for(int j=m-v[u];j>=0;j--)//循環(huán)體積,先給v[u]騰出位置來
for(int k=0;k<=j;k++)//循環(huán)決策,枚舉當(dāng)前用多少體積
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k]);//不要寫成w[i],是子樹的體積和質(zhì)量
}
//在體積為j時,再將當(dāng)前u加進(jìn)去
//相應(yīng)更新dp數(shù)組
for(int j=m;j>=v[u];j--)dp[u][j]=dp[u][j-v[u]]+w[u];
for(int j=0;j<v[u];j++) dp[u][j]=0;
}
int main()
{
int root;
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
int p;
cin>>v[i]>>w[i]>>p;
if(p==-1) root=i;
else
add(p,i);
}
dfs(root);
cout<<dp[root][m]<<endl;
return 0;
}
