Cod sursa(job #1773279)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 7 octombrie 2016 18:27:19
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define DIM 16005
using namespace std;
int n, i, x;
long long d[DIM], ff[DIM], w[DIM];
int ap[DIM];
vector<int> v[DIM];
ifstream fin("dosare.in");
ofstream fout("dosare.out");
void dfs(int nod){
    int i, vecin, m;
    for(i = 0; i < v[nod].size(); i++){
        dfs(v[nod][i]);
    }
    ff[nod] = ap[nod];
    m = v[nod].size();
    for(i = 0; i < m; i++){
        vecin = v[nod][i];
        d[nod] += d[vecin];
        w[i] = ff[vecin];
        ff[nod] += ff[vecin];
    }
    sort(w, w + m);
    for(i = m - 1; i >= 0; i--){
        d[nod] += w[i] * (m - i - 1);
    }
    d[nod] += ff[nod];
}
int main(){
    fin>> n;
    for(i = 2; i <= n; i++){
        fin>> x;
        v[x].push_back(i);
    }
    for(i = 1; i <= n; i++){
        fin>> ap[i];
    }
    dfs(1);
    fout<< d[1] <<"\n";
    return 0;
}