HDU 2196

hdu2196.cpp

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

using namespace std;
const int N = 10005;

vector<pair<int, long long> > a[N];
map<int, long long> dp[N];

long long DP(int u, int v, long long d) {
    if (dp[u].count(v)) {
        return dp[u][v];
    }
    long long tmp = 0;
    for (vector<pair<int, long long> >::iterator it = a[v].begin(); it != a[v].end(); it++) {
        int x = (*it).first;
        if (x != u)
            tmp = max(tmp, DP(v, x, (*it).second));
    }
    return dp[u][v] = tmp + d;
}

void init() {
    for (int i=0;i<N;i++) {
        a[i].clear();
        dp[i].clear();
    }
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        init();
        a[0].push_back(make_pair(1, 0));
        for (int i = 2; i <= n; i++) {
            int u;
            long long v;
            scanf("%d%lld", &u, &v);
            a[u].push_back(make_pair(i, v));
            a[i].push_back(make_pair(u, v));
            a[0].push_back(make_pair(i, 0));
        }

        for (int i = 1; i <= n; i++) {
            cout << DP(0, i, 0) << endl;

        }
    }
    return 0;
}