记录编号	123216	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011冲刺九]引爆炸弹	最终得分	100
用户昵称	Ezio	是否通过	通过
代码语言	C++	运行时间	0.475 s
提交时间	2014-09-26 09:40:11	内存使用	11.00 MiB

#include <iostream>
 #include <cstring>
 #include <cstdio>
 #include <cstdlib>
 #include <cctype>
 #include <cmath>
 #include <algorithm>
 #include <ctime>
 #define For(st,ed,i) for(int i=st;i<=ed;++i)
 #define Fordown(st,ed,i) for(int i=st;i>=ed;--i)
 #define start(a,flag) memset(a,flag,sizeof(a));
 using namespace std;
 typedef long long ll;typedef unsigned int uint; typedef unsigned long long ull;
 const int INF=0x7fffffff;
 const int inf=0xfffffff;
 const int MAXN=200001;
 ll f[MAXN],g[MAXN],a[MAXN],b[MAXN],s[MAXN],d[MAXN],v[MAXN];
 ll ans,t=0,n,k;
 void find(ll l,ll r){
 ll i,j,t,mid=f[s[(l+r)/2]];
 i=l;j=r;
 while(i<=j){
 while(f[s[i]]>mid)++i;
 while(f[s[j]]<mid)--j;
 if(i<=j){t=s[i];s[i]=s[j];s[j]=t;++i;--j;}
 }
 if(l<j)find(l,j);if(i<r)find(i,r);
 return; 
 }
 void go()
 {
 ll i,j;
 while(t!=0){
 i=t;t=d[i];f[i]=b[i]+f[i];
 if(a[i]!=0){
 if(f[a[i]]<f[i])
 {f[a[i]]=f[i];g[a[i]]=i;}
 d[a[i]]--;
 if(d[a[i]]==0)
 {d[a[i]]=t;t=a[i];}}}
 For(1,n,i)s[i]=i;
 find(1,n);ans=0;
 For(1,n,i){
 if(v[s[i]]==0){
 ans+=f[s[i]];--k;
 if(k==0)break;j=s[i];
 while(j!=0){v[j]=1;j=g[j];}}}
 return;
 }
 int main()
 {
 freopen("bombb.in","r",stdin);
 freopen("bombb.out","w",stdout);
 scanf("%lld%lld",&n,&k);
 For(1,n,i){scanf("%lld%lld",&a[i],&b[i]);d[a[i]]++;}
 For(1,n,i)if(d[i]==0){d[i]=t;t=i;}
 go();
 printf("%lld",ans);
 //system("pause");
 return 0;
 }