Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2009-day4 Distribution

問題文 : 冊子の配布

解法 :
得られるやる気を最大化したいので, 葉まで冊子を流し, その中の最大値を取っていけば良い.
つまり、葉までやる気を伝搬させれば良い.
この操作をM回繰り返す.

木の操作、最大値の取得をO(N)時間で行うことで, O(MN)時間でこの問題を解くことが出来る.

コード :

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> g[10000];
int mood[10000];
int tot[10000];
int par[10000];

int makeMax(int v, int s)
{
	s += mood[v];
	tot[v] = s;
	for (int i = 0; i < g[v].size(); i++){
		makeMax(g[v][i], s);
	}
}

int main()
{
	int n, m;
	int res;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++){
		int a;
		scanf("%d %d", &a, &mood[i]);
		a--;
		if (~a) g[a].push_back(i);
		par[i] = a;
	}
	
	int ans = 0;
	for (int i = 0; i < m; i++){
		makeMax(0, 0);
		int mP, mV;
		mP = mV = -1;
		for (int j = 0; j < n; j++){
			if (tot[j] > mV){
				mV = tot[j]; mP = j;
			}
		}
		ans += mV;
		for (; ~mP; mP = par[mP]){
			mood[mP] = 0;
		}
	
	}
	
	printf("%d\n", ans);
	
	return (0);
}