JOI春合宿 2008-day1 committee

問題文 : 委員会(pdf注意, 1-2ページ目)

解法 :
各頂点ごとに, やる気の最大値をメモする. 答えは, やる気の最大値が最も大きい頂点となる.
ある頂点のやる気の最大値は, 自分自身のやる気＋自分の子までのやる気の最大値のうち, 負で無いものの和, として求まる.

ここで, やる気の最大値を0で初期化してはいけないことに注意する(やる気が全て負になる場合があることに注意する.)

コード :

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

#define MAX_N (100000)

using namespace std;

vector<int> g[MAX_N];
int mood[MAX_N];
int sum[MAX_N];

int make(int v)
{
	int t = mood[v];
	
	for (int i = 0; i < g[v].size(); i++){
		int c = make(g[v][i]);
		t += (c > 0 ? c : 0);
	}
	return (sum[v] = t);
}

int main()
{
	int n;
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		int a;
		scanf("%d %d", &a, mood + i);
		a--;
		if (~a) g[a].push_back(i);
	}
	
	make(0);
	
	int res = sum[0];
	for (int i = 1; i < n; i++){
		res = max(res, sum[i]);
	}
	
	printf("%d", res);
	
	return (0);
}