记录编号	128380	评测结果	AAAAAAAAAA
题目名称	[郑州101中学] 圣战	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	1.030 s
提交时间	2014-10-17 15:53:16	内存使用	51.07 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int i,n,m,zj1,zj2,s[10010]={0},fff[10001][501]={0},tree[10001][901]={0},l[10010]={0},r[10010]={0};
void Build(int fa)
{
	if(!tree[fa][0]) return;
	l[fa]=tree[fa][1];
	Build(l[fa]);
	int h=l[fa];
	for(int x=2;x<=tree[fa][0];x++)
	{
		r[h]=tree[fa][x];
		h=r[h];
		Build(h);
	}
}
void init()
{
	scanf("%d%d",&m,&n);
	m++;
	for(i=2;i<=m;i++)
	{
		scanf("%d%d",&zj1,&s[i]);
		zj1++;
		tree[zj1][0]++;
		tree[zj1][ tree[zj1][0] ]=i;
	}
}
void Tree_DP(int fa)
{
	if(l[fa])Tree_DP(l[fa]);
	if(r[fa])Tree_DP(r[fa]);
	int h,x;
	for(int z=1;z<=n;z++)
	{
		fff[fa][z]=fff[r[fa]][z];
		for(x=0;x<z;x++)
		{
			h=fff[l[fa]][x]+fff[r[fa]][z-x-1]+s[fa];
			if(fff[fa][z]<h)fff[fa][z]=h;
		}
	}
}
void PRINT()
{
	fff[1][n]+=40000000;
	int k=fff[1][n];
	printf("%d\n",k);
}
int main()
{
	freopen("charge.in","r",stdin);
	freopen("charge.out","w",stdout);
	init();//get
	Build(1);//get
	Tree_DP(1);
	PRINT();
	return 0;
	fclose(stdin);
	fclose(stdout);
}