Cod sursa(job #3038223)

Utilizator rastervcrastervc rastervc Data 26 martie 2023 23:21:18
Problema Dosare Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

constexpr size_t LIM = 16005;
int N, father, score, cnt[LIM];
vector<int> G[LIM];

inline void dfs(int node, int father) {
    for (const int adj : G[node])
        if (adj != father) dfs(adj, node);

    sort(G[node].begin(), G[node].end(), [](int node1, int node2) {
        return cnt[node1] > cnt[node2];
    });
    for (int i = 0; i < G[node].size(); ++i) {
        cnt[node] += cnt[G[node][i]];
        score += (i + 1) * cnt[G[node][i]];
    }
}

int main() {
    fin >> N;
    for (int i = 2; i <= N; ++i) {
        fin >> father;
        G[father].push_back(i);
    }
    for (int i = 1; i <= N; ++i)
        fin >> cnt[i];

    dfs(1, 0);
    score += cnt[1];

    fout << score;

    fin.close();
    fout.close();
    return 0;
}