Cod sursa(job #2102159)

Utilizator luanastLuana Strimbeanu luanast Data 8 ianuarie 2018 14:42:22
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("dosare.in");
ofstream fout ("dosare.out");
int n,i,x,ac[100010];
long long D[100010],sons[100010];
vector <int> L[100001];

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

void dfs (int nod){
    sons[nod]=ac[nod];
    for(int i=0;i<L[nod].size();i++){
        dfs(L[nod][i]);
        sons[nod]+=sons[L[nod][i]];
    }
    //daca nod are fii, il sortam descrescator dupa sons
    //in dinamica tinem nr total de apasari daca nod ar fi radacina
    D[nod]=sons[nod];
    int c=L[nod].size();
    if(c){
        sort(L[nod].begin(), L[nod].end(), cmp);
        for(int i=0;i<L[nod].size();i++)
            D[nod]+=i*sons[L[nod][i]]+D[L[nod][i]];
    }

}


int main(){
    fin>>n;
    for(i=2;i<=n;i++){
        fin>>x;
        L[x].push_back(i);
    }
    for(i=1;i<=n;i++)
        fin>>ac[i];
    dfs(1);
    fout<<D[1];
    return 0;
}