Cod sursa(job #1773021)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 7 octombrie 2016 14:31:08
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream in ( "dosare.in"  );
ofstream out( "dosare.out" );

const int DIM = 2e4 + 5;
const int INF = 1e9 + 7;

vector<int> g[DIM];
long long dp[DIM];

bool comp( int x, int y ) {
    return dp[x] > dp[y];
}

void dfs( int x, long long &ans ) {

    for( auto y : g[x] ) {
        dfs( y, ans );
        dp[x] += dp[y];
    }

    sort( g[x].begin(), g[x].end(), comp );
    ans += dp[x]; int k = 0;

    for( auto y : g[x] )
        ans += (k ++) * 1LL * dp[y];

    return;
}

int main( int argc, const char *argv[] ) {

    int n; long long ans = 0; in >> n;

    for( int i = 2; i <= n; i ++ ) {
        int x; in >> x;
        g[x].push_back( i );
    }

    for( int i = 1; i <= n; i ++ )
        in >> dp[i];

    dfs( 1, ans );
    out << ans << endl;

    return 0;
}