Cod sursa(job #3260057)

Utilizator rares89_Dumitriu Rares rares89_ Data 29 noiembrie 2024 21:40:16
Problema Dosare Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <vector>
#include <algorithm> // sort

using namespace std;

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

int n, ans, dp[16005]; // dp[i] - nr total de accesari in subarborele cu radacina i
int moves[16005];
vector<int> G[16005];

void dinamica(int nod) {
    for(auto i : G[nod]) {
        dinamica(i);
        dp[nod] += dp[i];
    }
    // Construiesc arborele astfel incat sa am cat mai in stanga
    // Cat mai multe foldere, pentru a avea nr minim de reveniri
    sort(G[nod].begin(), G[nod].end(), [](int x, int y) {
        return dp[x] > dp[y]; 
    });
}

// Calculez mutarile cu reveniri
// De exemplu daca mai intai parcurg subarborele stang
// Contorizez si revenirea la radacina plus move-ul catre subarorele drept
void dfs(int nod, int currentMoves) {
    ans += moves[nod] * currentMoves;
    for(int i = 0; i < G[nod].size(); ++i) {
        dfs(G[nod][i], i + currentMoves + 1);
    }
}

int main() {
    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) {
        int x;
        fin >> x;
        dp[i] = moves[i] = x;
    }
    dinamica(1);
    dfs(1, 1); // Apas enter prima oara, deci 1 move
    fout << ans;
    return 0;
}