Cod sursa(job #3342632)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 25 februarie 2026 09:00:38
Problema Dosare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

const int NMAX = 16'000;

int n;
ll answer;
int a[NMAX + 1];
vector<int> g[NMAX + 1];
ll sub[NMAX + 1];

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

void DFS1(int node) {
    sub[node] = a[node];
    for(int next_node : g[node]) {
        DFS1(next_node);
        sub[node] += sub[next_node];
    }
}

void DFS2(int node, int steps = 1) {
    answer += (ll) a[node] * steps;

    sort(g[node].begin(), g[node].end(), cmp);
    int i = 1;
    for(int next_node : g[node]) {
        DFS2(next_node, steps + i);
        i++;
    }
}

int main() {
    fin >> n;
    for(int i = 2; i <= n; i++) {
        int p;
        fin >> p;
        g[p].push_back(i);
    }

    for(int i = 1; i <= n; i++) {
        fin >> a[i];
    }

    DFS1(1);
    DFS2(1);
    fout << answer << '\n';
    return 0;
}