记录编号	328103	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011冲刺九]引爆炸弹	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	0.748 s
提交时间	2016-10-23 18:54:16	内存使用	5.65 MiB

/*
其实思路主要是卡在炸弹不能引爆两次，对于炸弹由什么地方引爆的没有思路。
但是其实想明白了也很好解决，对于每一个炸弹，只能有一个爆炸来源，所以我们反向建边，
我们找出每一个节点的最大的来源，然后把这些价值排序，取前k个；
*/ 
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
#define ll long long
#define inf 1061109567
#define maxn 200010
int in[maxn],b[maxn],len,head[maxn];
ll val[maxn];
struct edge{
	int to,next;
}a[maxn];
void insert(int x,int y){
	len++;a[len].to=y;a[len].next=head[x];head[x]=len;
}
ll dfs(int pos){
    val[pos]=b[pos];
    int tpos=0;
    for(int i=head[pos];i;i=a[i].next){
        int t=a[i].to;
        dfs(t);
        if(val[t]+b[pos]>val[pos]){
            val[pos]=val[t]+b[pos];
            tpos=t;
        }
    }
    val[tpos]=0;
}
int main(){
    freopen("bombb.in","r",stdin);
    freopen("bombb.out","w",stdout);
    int n,k,a;scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
		int x;
        scanf("%d%d",&x,&b[i]);
        if(x!=0){
            in[i]++;
            insert(x,i);
        }
    }
    for(int i=1;i<=n;i++)if(!in[i])dfs(i);
    sort(val+1,val+1+n);
    ll ans=0;
    while(n&&k){
        ans+=val[n];
        n--;k--;
    }
    printf("%lld\n",ans);
    //while(1);
}