Cod sursa(job #2113014)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 24 ianuarie 2018 09:44:50
Problema Dosare Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream in ("dosare.in");
ofstream out ("dosare.out");
long long d[16001],howmany[16001],c[16001],n,x;
vector<int> v[16001];
bool cmp (int a, int b) {
    return d[a] > d[b];
}
void dinamica (int nod) {
    for (int i = 0; i < v[nod].size(); i ++) {
        int vecin = v[nod][i];
        dinamica (vecin);
        howmany[nod] += howmany[vecin];
    }
    howmany[nod] += c[nod];
}
void dfs (int nod) {
    int aux[16001];
    for (int i = 0; i < v[nod].size(); i++) {
        int vecin = v[nod][i];
        dfs (vecin);
        aux[i] = vecin;
    }
    sort (aux+0,aux+v[nod].size(),cmp);
    for (int i = 0; i < v[nod].size(); i ++) {
        d[nod] += (i+1)*howmany[aux[i]] + d[aux[i]];
    }
    d[nod] += c[nod];
}
int main (void) {
    in >> n;
    for (int i = 2; i <= n; i ++) {
        in >> x;
        v[x].push_back (i);
    }
    for (int i = 1; i <= n; i ++) {
        in >> c[i];
    }
    dinamica(1);
    dfs (1);
    out << d[1];
    return 0;
}