Cod sursa(job #1743992)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 19 august 2016 02:21:00
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream cin("dosare.in");
ofstream cout("dosare.out");

const int MAXN = 16000;

vector<int> g[1 + MAXN];
long long answer, cost[1 + MAXN];

void DFS(int node) {
    vector<long long> sons;
    for (auto &son : g[node]) {
        DFS(son);
        cost[node] += cost[son];
        sons.push_back(cost[son]);
    }
    sort(sons.begin(), sons.end());
    answer += cost[node];
    for (int i = sons.size() - 1; i >= 0; i--)
        answer = answer + 1LL * (sons.size() - i - 1) * sons[i];
}

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        g[x].push_back(i);
    }
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
    DFS(1);
    cout << answer << "\n";
    return 0;
}