记录编号	45043	评测结果	AAAAAAAAAA
题目名称	[郑州101中学] 圣战	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	1.438 s
提交时间	2012-10-22 07:48:21	内存使用	22.82 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int val[10010],sonnum[10010],f[10010][510];
vector<int> son[10010];

int maxint(int a,int b)
{
    if (a>b)
        return(a);
    return(b);
}

void fillit(int pos,int limit)
{
	int i,j,k;
	for (i=0;i<sonnum[pos];i++)
	{
		fillit(son[pos][i],limit-1);
		for (j=limit-1;j>=1;j--)
		{
			for (k=1;k<=j;k++)
			{
				f[pos][j]=maxint(f[pos][j],f[pos][j-k]+f[son[pos][i]][k]);
			}
		}
	}
	for (i=limit;i>=1;i--)
		f[pos][i]=f[pos][i-1]+val[pos];
}

int main(void)
{
    freopen("charge.in","r",stdin);
    freopen("charge.out","w",stdout);
    int i,n,lim,temp;
    cin>>n>>lim;
    val[0]=40000000;
    for (i=1;i<=n;i++)
    {
        cin>>temp>>val[i];
        sonnum[temp]++;
        son[temp].push_back(i);
    }
    fillit(0,lim);
    cout<<f[0][lim]<<endl;
    return(0);
}