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