貪欲法
計算量がO(NM)でNM = 10^7だから「計算量ちょっとやばいかなー」と思ってできるだけ高速に実行できるように頑張ったけど実際そんなことやる必要なかった問題。

#include <bits/stdc++.h>

using namespace std;

int n,m,co,ans,yaruki[10003],ruisekiyaruki[10003],oya[10003],kouho[10009];
vector<int> ko[10003];
void ddfs(int nau,int hiku){
	ruisekiyaruki[nau] -= hiku;
	for(int i = 0;i < ko[nau].size();i++){
		ddfs(ko[nau][i],hiku);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	int s,a;
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&s,&a);
		ko[s].push_back(i);
		yaruki[i] = a;
		oya[i] = s;
	}
	for(int i = 1;i <= n;i++){
		ruisekiyaruki[i] += yaruki[i];
		for(int j = 0;j < ko[i].size();j++){
			int k = ko[i][j];
			ruisekiyaruki[k] += ruisekiyaruki[i];
		}
		if(ko[i].empty()) kouho[co++] = i;
	}
	while(m--){
		int c = -1,ban;
		for(int i = 0;i < co;i++){
			if(c < ruisekiyaruki[kouho[i]]){
				c = ruisekiyaruki[kouho[i]];
				ban = i;
			}
		}
		if(c == -1)break;
		ans += c;
		ruisekiyaruki[kouho[ban]] = -1;
		int nau = oya[kouho[ban]];
		while(nau != 0){
			if(ruisekiyaruki[nau] == -1)break;
			for(int j = 0;j < ko[nau].size();j++){
				if(ruisekiyaruki[ko[nau][j]] == -1)continue;
				ddfs(ko[nau][j],ruisekiyaruki[nau]);
			}
			ruisekiyaruki[nau] = -1;
			nau = oya[nau];
		}
	}
	printf("%d
",ans);
	return 0;
}