hdu1561The more, The Better 樹形dp
/*
dp[i][j]表示第i個節點及其子樹取j個所得的最大值
在第i個節點的兒子節點有多個，而對於每個兒子節點及其對應的子樹中選幾個節點才能得到最大值
可以用背包來做
*/
#include
#include
#include
#include
using namespace std;
#define maxn 210
int dp[maxn][maxn];//dp[i][j]表示第i個節點及其子樹取j個所得的最大值
int value[maxn];
int vis[maxn];
vector vec[maxn];
int N,M;
int dfs(int root,int remain)//remain表示到了這個節點最多能選多少節點
{
int i;int j,k;
int amount=0;//表示以該節點為根節點的子樹的所有的節點的個數
for(i=0;i
{
int next=vec[root][i];
int sum;
sum=dfs(next,remain-1);//表示這個這個子樹的節點總數
amount+=sum;
for(j=min(remain-1,amount);j>=1;j--)
for(k=1;k<=sum&&k<=j;k++)
dp[root][j]=max((dp[root][j-k]+dp[next][k]),dp[root][j]);
}
for(j=min(amount,remain-1);j>=0;j--)//只能選了這個節點後才能選後面的節點
dp[root][j+1]=dp[root][j]+value[root];//所以該節點一定要加上
return amount+1;
}
int main()
{
/*freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);*/
while(scanf("%d%d",&N,&M),N||M)
{
int a,b;int i;
memset(value,0,sizeof(value));
memset(dp,0,sizeof(dp));
for(i=0;i<=N;i++)
vec[i].clear();
for(i=1;i<=N;i++)
{
scanf("%d%d",&a,&b);
vec[a].push_back(i);
value[i]=b;
}
dfs(0,M+1);
printf("%d\n",dp[0][M+1]);
}
return 0;
}
