Cod sursa(job #1996689)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 2 iulie 2017 13:41:03
Problema Dosare Scor 100
Compilator cpp Status done
Runda Simulare 18a Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int nmax = 16e3;
long long d[nmax + 1];

vector< int > ord;
vector< int > g[nmax + 1];

void dfs (int nod) {
    ord.push_back( nod );
    for (auto i : g[ nod ]) {
        dfs( i );
    }
}

inline bool cmp (int x, int y) {
    return d[ x ] > d[ y ];
}

int main() {
    int n;
    fin >> n;

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

    for (int i = 1; i <= n; ++ i) {
        fin >> d[ i ];
    }

    dfs( 1 );

    for (int j = (int)ord.size() - 1; j >= 0; -- j) {
        int x = ord[ j ];
        for (auto i : g[ x ]) {
            d[ x ] += d[ i ];
        }

        sort(g[ x ].begin(), g[ x ].end(), cmp);
    }

    long long ans = d[ 1 ];
    for (auto j : ord) {
        for (int i = 0; i < (int)g[ j ].size(); ++ i) {
            ans += d[ g[ j ][ i ] ] * (i + 1);
        }
    }

    fout << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}