APIO2012 Dispatching

今思えば簡単だった…

各ノードにたいして持っておくのはpriority_queue。中身の合計も別に持っておく。
DFS調に下から各ノードに対して満足度を求めていく。大事なこととして、
「最初にpriority_queueに子ノードたちのぶんを合体させて持っておく。(いぱテクを使う)」
「そのpriority_queueの中身の合計がMを下回るまで大きい順にpopして追い出していく」
これで合計O(n log^2 n)で解ける。segtreeとかそういうのいらないです。

ちなみに、APIO2012の問題はここにオンラインジャッジがあります。(韓国語です)
http://www.acmicpc.net/

ソースコード

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
vector<int>g[101000];
int c[101000];
int d[101000];
long long sum[101000];
priority_queue<int> Q[101000];
int par[101000];
int ne;
int b;
long long ret=0LL;
void solve(int a){
	for(int i=0;i<g[a].size();i++){
		solve(g[a][i]);
		if(Q[par[a]].size()<Q[par[g[a][i]]].size()){
			while(Q[par[a]].size()){
				Q[par[g[a][i]]].push(Q[par[a]].top());
				Q[par[a]].pop();
			}
			sum[par[g[a][i]]]+=sum[par[a]];
			par[a]=par[g[a][i]];
		}else{
			while(Q[par[g[a][i]]].size()){
				Q[par[a]].push(Q[par[g[a][i]]].top());
				Q[par[g[a][i]]].pop();
			}
			sum[par[a]]+=sum[par[g[a][i]]];
		}
	}
	
	while(sum[par[a]]>b){
		sum[par[a]]-=Q[par[a]].top();
		Q[par[a]].pop();
	}
	ret=max(ret,(long long)d[a]*(long long )Q[par[a]].size());
}
int main(){
	int a;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		if(p==0)ne=i;
		else g[p-1].push_back(i);
		c[i]=q;
		d[i]=r;
		Q[i].push(q);
		par[i]=i;
		sum[i]=q;
	}
	solve(ne);
	printf("%lld\n",ret);
}