Cod sursa(job #2973829)

Utilizator AlexNicuNicu Alexandru AlexNicu Data 2 februarie 2023 12:40:35
Problema Dosare Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

#define NMAX 16005

vector<int> G[NMAX];
int dist[NMAX];
bool viz[NMAX];
int cost[NMAX];

int sp[NMAX];

bool cmp ( int a, int b ) {
    return sp[a] > sp[b];
}

int sum;

void dfs( int node ) {
    viz[node] = true;
    vector<int> fii;
    for ( int child : G[node] ) {
        if ( viz[child] == false )
          fii.push_back(child);
    }
    for ( int child : G[node] ) {
        if ( viz[child] == false )
          dfs(child);
    }
    sort( fii.begin(), fii.end(), cmp );
    for ( int i = 0; i < fii.size(); i++ ) {
        sum += ( i + 1 ) * sp[fii[i]];
        sp[node] += sp[fii[i]];
    }
}

int main() {
    int n, i, parent, st, dr;
    cin >> n;
    for ( i = 2; i <= n; i++ ) {
        cin >> parent;
        G[parent].push_back(i);
        G[i].push_back(parent);
    }
    for ( i = 1; i <= n; i++ ) {
        cin >> cost[i];
        sp[i] = cost[i];
    }
    dfs(1);
    cout << sum + sp[1] << "\n";
    return 0;
}