IOI '14 P5 - Friend (Standard I/O)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> p(n), q(n), h(n), type(n);
    for (int &x : p) cin >> x; // p is benefit from choosing, q is benefit from not choosing
    for (int i = 1; i < n; ++i) cin >> h[i] >> type[i];
    for (int i = n-1; i > 0; --i) {
        if (type[i] == 0) { // IAmYourFriend
            p[h[i]] += q[i];
            q[h[i]] += max(p[i], q[i]);
        } else if (type[i] == 1) { // MyFriendsAreYourFriends
            p[h[i]] += max(p[i], q[i]);
            q[h[i]] += q[i];
        } else { // WeAreYourFriends
            p[h[i]] = max(p[h[i]] + q[i], p[i] + q[h[i]]);
            q[h[i]] += q[i];
        }
        p[h[i]] = max(p[h[i]], q[h[i]]); // not choosing never makes things worse
    }
    cout << max(p[0], q[0]) << endl;
    return 0;
}