Cod sursa(job #1766033)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 27 septembrie 2016 12:21:48
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int dim = 16005;

vector<int> g[dim];
int countAccess[dim];
long long dp[dim];

long long ans = 0;
void DFS(int node) {

    vector< long long > countSons;
    dp[node] = countAccess[node];
    for (auto adj : g[node]) {
        DFS(adj);
        countSons.push_back(dp[adj]);
        dp[node] += dp[adj];
    }

    ans += dp[node];
    sort(countSons.begin(), countSons.end());
    reverse(countSons.begin(), countSons.end());

    for (size_t i = 0; i < countSons.size(); ++i)
        ans += 1LL * countSons[i] * i;

}

int main() {

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

    DFS(1);
    fout << ans << '\n';

    return 0;

}

//Trust me, I'm the Doctor!