Algoogle

Algorithm for Programming Contest

JOI 春合宿 2008 Committee

Category: JOI Tag: dp

Committee

問題概要


上司が親の根付き木が与えられる.
連結な部分を取り出したときの各ノードのやる気の総和の最大を求めよ.
ただし頂点はかならず1つ以上含むこと.

解法


簡単な木DP
木の葉の子から親にやる気を順に足していけば良い. ただし子のやる気が負の時は足さない方がいいので足さない.

コード


(Committee.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int n, y[100010], p[100010], ans;

int solve()
{
        ans = -100;
        for (int i = n; i > 0; i--){
                ans = max(ans, y[i]);
                if(y[i] > 0) y[p[i]] += y[i];
        }

        return ans;
}

void input()
{
        cin >> n;
        for (int i = 0; i < n; i++)
                cin >> p[i+1] >> y[i+1];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments