Cod sursa(job #2648149)

Utilizator felixiPuscasu Felix felixi Data 8 septembrie 2020 23:25:41
Problema Dosare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 16e3;

vector<int> G[NMAX + 5];
long long N, dp[NMAX + 5], sum[NMAX + 5];

void dfs(int node, int tata = -1)
{
    // cerr << node << '\n';
    vector<int> sons;
    for (int x : G[node]) {
        if (x == tata)
            continue;
        dfs(x, node);
        sons.push_back(x);
        sum[node] += sum[x];
    }
    sort(sons.begin(), sons.end(), [](int a, int b){
        return sum[a] > sum[b];
    });
    for (int i = 0; i < (int)sons.size(); ++i) {
        dp[node] += dp[sons[i]] + i * sum[sons[i]];
    }
    dp[node] += sum[node];
}

int main()
{
    in >> N;
    // cerr << "N = " << N << '\n';
    for (int i = 2; i <= N; ++i) {
        int par;
        in >> par;
        G[i].push_back(par);
        G[par].push_back(i);
    }
    for (int i = 1; i <= N; ++i) {
        in >> sum[i];
    }
    dfs(1);
    out << dp[1] << '\n';
    return 0;
}