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; }