记录编号	46646	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011冲刺九]引爆炸弹	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	1.507 s
提交时间	2012-10-29 09:17:06	内存使用	9.02 MiB

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

int waynum[200010],waycomenum[200010];
long long val[200010],f[200010];
vector<int> wayto[200010];

void fillit(int pos)
{
	int i,to,temp,tempto=0;
	if (f[pos]<val[pos]);
		f[pos]=val[pos];
	for (i=0;i<waynum[pos];i++)
	{
		to=wayto[pos][i];
		fillit(to);
		temp=f[to]+val[pos];
		if (f[pos]<temp)
		{
			f[pos]=temp;
			tempto=to;
		}
	}
	f[tempto]=0;
}

int main(void)
{
	freopen("bombb.in","r",stdin);
	freopen("bombb.out","w",stdout);
	int i,j,n,k,temp;
	long long total=0;
	cin>>n>>k;
	for (i=1;i<=n;i++)
	{
		cin>>temp>>val[i];
		if (temp!=0)
		{
			waycomenum[i]++;
			waynum[temp]++;
			wayto[temp].push_back(i);
		}
	}
	for (i=1;i<=n;i++)
		if (waycomenum[i]==0)
			fillit(i);
	sort(f,f+n+1);
	for (i=n,j=1;i>=0&&j<=k;i--,j++)
		total+=f[i];
	cout<<total<<endl;
	return(0);
}