Task J - 09.03.2019

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
////////////

const int sz = 1e6 + 10;
int n;
ll w[sz];
vector<int> g[sz];
ll depth[sz];
bool used[sz];

///////////


void dfs(int f){
    used[f] = true;
    for(int v : g[f]){
        if(!used[v]){
            dfs(v);
            depth[f] += depth[v];
        }
    }
    depth[f] += w[f];
}

vector<pair<ll ,int> > gw[sz];

ll dfsAns(int f, int e = 0){
    used[f] = true;
    ll ans = 0;
    int cursz = gw[f].size() - 1;
    for(int  i = 0; i<gw[f].size(); i++){
        if(!used[gw[f][i].second])
        ans += dfsAns(gw[f][i].second, cursz - i);
    }
    ans += depth[f] * e;
    return ans;
}

void solve() {
    cin>>n;
    memset(depth, 0, sizeof depth);
    memset(used, 0, sizeof used);
    for(int i=0;i<n;i++){
        int f,t;
        cin>>w[i]>>f;
        if(f!=-1){
            g[f].push_back(i);
            g[i].push_back(f);
        }
    }
    for(int i=0;i<n;i++){
        if(!used[i]) dfs(i);
    }

    for(int i=0;i<n;i++){
        for(int t : g[i]){
            if(depth[t] < depth[i])
            gw[i].push_back({depth[t],t});
        }
        sort(gw[i].begin(), gw[i].end());
    }
    ll ans = 0;

    memset(used, 0, sizeof used);
    for(int i=0;i<n;i++){
        if(!used[i]){
            ans += dfsAns(i);
        }
    }
    cout<<ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}