/*
分组背包+树形dp：以树的深度作为阶段，以节点编号作为一维状态，
思路：首先dp[u][t]表示选择以第u门课为根，选了t门课的最大值，
状态转移方程dp[u][t]=max(所有儿子中凑出t-1门课)+s[u]，
那么如何在所有儿子中凑出t-1门课，需要用到分组背包，每个儿子为一组，设v是u的一个儿子,那么第v组背包中有t-1件物品，第j件物品体积为j，价值就是dp[v][j](以v为根的选了j门课的最大值)
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,dp[
305][
305],s[
305];
vector<
int> son[
305];
void dfs(
int u){
dp[u][0]=
0;
for(
int i=
0;i<son[u].size();i++
){
int v=
son[u][i];
dfs(v);
for(
int t=m;t>=
0;t--)
//状态：分组背包逆序循环背包容量
for(
int j=
0;j<=t;j++)
//决策：为什么进阶指南上要求对决策进行逆序遍历？
dp[u][t]=max(dp[u][t],dp[u][t-j]+
dp[v][j]);
}
if(u!=
0)
//必须算上这门课
for(
int t=m;t>
0;t--
)
dp[u][t]=dp[u][t-
1]+
s[u];
}
int main(){
while(scanf(
"%d%d",&n,&m)==
2){
for(
int i=
1;i<=n;i++
){
int u;
scanf("%d%d",&u,&
s[i]);
son[u].push_back(i);
}
dfs(0);
printf("%d\n",dp[
0][m]);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10223733.html
