読者です 読者をやめる 読者になる 読者になる

JOI 2009 春合宿 day4-1 「Distribution」

Committeeと同じ要領。
こっちはやる気が1以上と決まっているのでその点は楽。
2009ってday4よりday3の方がムズくね? Starry SkyはなんかBLっぽいから知らん。

#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define pb push_back
using namespace std;

vector<int> c[10001];
int a[10001], dp[10001][1001], n, m;

void f(int v){
	priority_queue<int> q;
	
	rep(i,c[v].size()){
		f(c[v][i]);
		for(int j = 1; j <= m && dp[c[v][i]][j]; j++) q.push(dp[c[v][i]][j]);
	}
	
	for(int i = 1; i <= m && !q.empty(); i++){
		dp[v][i] = q.top();
		q.pop();
	}
	
	dp[v][1] += a[v];
	
	return;
}


int main(){
	int s, ans = 0;
	
	scanf("%d%d",&n,&m);
	
	rrep(i,n){
		scanf("%d%d",&s,&a[i]);
		c[s].pb(i);
	}
	
	f(1);
	
	for(int i = 1; dp[1][i]; i++) ans += dp[1][i];
	
	printf("%d\n",ans);
	
	return 0;
}