Cod sursa(job #2100016)

Utilizator mariusn01Marius Nicoli mariusn01 Data 4 ianuarie 2018 23:58:35
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define DIM 100010

using namespace std;

vector<int> L[DIM];

long long D[DIM], S[DIM];
int c[DIM];
int n, x;
long long sol;

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

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

void dfs(int nod) {
    D[nod] = 0;
    S[nod] = c[nod];

    for (int i=0;i<L[nod].size();i++) {
        int fiu = L[nod][i];
        dfs( fiu );
        S[nod] += S[fiu];
    }

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

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

    for (int i=1;i<=n;i++)
        fin>>c[i];

    dfs(1);

    fout<<D[1];
    return 0;
}