Selectivo 2 - P6

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

using namespace std;

#define MAXN 500000

vector<int> L[MAXN],W[MAXN];
int best[MAXN][2];

void fix(int x){
    if(best[x][1] > best[x][0])
        swap(best[x][0],best[x][1]);
}

int ans;

void dfs(int cur, int p){
    best[cur][0] = best[cur][1] = -500000000;

    for(int i = L[cur].size() - 1,to;i >= 0;--i){
        to = L[cur][i];

        if(to != p){
            dfs(to,cur);

            int aux = W[cur][i] + max(best[to][0],0);

            if(aux > best[cur][1]){
                best[cur][1] = aux;
                fix(cur);
            }
        }
    }

    ans = max(ans,best[cur][0] + best[cur][1]);
    ans = max(ans,best[cur][0]);
}

int main(){
    int n;

    while(true){
        scanf("%d",&n);
        if(n == 0) break;

        for(int i = 0;i < n;++i){
            L[i].clear();
            W[i].clear();
        }

        for(int i = 1,u,p;i < n;++i){
            scanf("%d %d",&u,&p);

            L[i].push_back(u);
            W[i].push_back(p);

            L[u].push_back(i);
            W[u].push_back(p);
        }

        ans = 0;
        dfs(0,-1);

        printf("%d\n",ans);
    }

    return 0;
}