Cod sursa(job #1382853)

Utilizator assa98Andrei Stanciu assa98 Data 9 martie 2015 17:14:30
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

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

const int MAX_N = 16100;


vector<int> A[MAX_N];

long long p[MAX_N];

long long ans = 0;

void dfs(int nod, int h) {
    ans += h * p[nod];
    vector<long long> v;
    for(auto it : A[nod]) {
        dfs(it, h + 1);
        v.push_back(p[it]);
        p[nod] += p[it];
    }
    sort(v.begin(), v.end(), greater<long long>());
    for(int i = 0; i < (int)v.size(); i++) {
        ans += v[i] * i;
    }
}

int main() {
    int n; 
    fin >> n;
    for(int i = 2; i <= n; i++) {
        int a;
        fin >> a;
        A[a].push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        fin >> p[i];
    }

    dfs(1, 1);
    fout << ans;
    return 0;
}