Cod sursa(job #1766025)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 27 septembrie 2016 12:06:25
Problema Dosare Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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], dp[dim];

long long DFS(int node) {

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

    long long ret = countAccess[node];
    sort(countSons.begin(), countSons.end());
    reverse(countSons.begin(), countSons.end());

    for (size_t i = 0; i < countSons.size(); ++i) {

        ret += countSons[i].first + 1LL * dp[countSons[i].second] * (1 + i);

    }

    return ret;

}

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];

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

    return 0;

}

//Trust me, I'm the Doctor!