Cod sursa(job #2102316)

Utilizator osiaccrCristian Osiac osiaccr Data 8 ianuarie 2018 17:30:57
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define DEF 100010
#define INF 1 << 29

using namespace std;

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

int n, co[DEF];

unsigned long long fii[DEF], sol[DEF];

vector < int > L[DEF];

bool cmp (int a, int b) {
    return fii[a] > fii[b];
}

void dfs (int nod) {
    fii[nod] = co[nod];
    for (int i = 0; i < L[nod].size (); ++ i) {
        dfs (L[nod][i]);
        fii[nod] += fii[L[nod][i]];
    }

    sol[nod] = fii[nod];
    if (L[nod].size ()) {
        sort (L[nod].begin (), L[nod].end (), cmp);
        for (int i = 0; i < L[nod].size (); ++ i) {
            sol[nod] += i * fii [L[nod][i]] + sol[L[nod][i]];
        }
    }
}

int main() {
    fin >> n;

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

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

    dfs (1);

    fout << sol[1];

    return 0;
}