Cod sursa(job #2020896)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 11 septembrie 2017 23:59:08
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define MAXN 16000

long long s[MAXN + 1];
int dp[MAXN + 1], a[MAXN + 1];

vector <int> g[MAXN + 1];

long long ans;

bool cmp(const int &a, const int &b) {
    return s[a] > s[b];
}

void dfs1(int x) {
    s[x] = a[x];
    for (auto &y : g[x]) {
        dfs1(y);
        s[x] += s[y];
    }
}

void dfs2(int x) {
    dp[x]++;
    ans += 1LL * a[x] * dp[x];
    sort(g[x].begin(), g[x].end(), cmp);
    for (int i = 0; i < (int)g[x].size(); i++) {
        dp[g[x][i]] = dp[x] + i;
        dfs2(g[x][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 >> a[i];

    dfs1(1);
    dfs2(1);

    fout << ans;

    return 0;
}