Cod sursa(job #3183418)

Utilizator PetraPetra Hedesiu Petra Data 11 decembrie 2023 19:58:12
Problema Dosare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

#define NMAX 16003

using namespace std;

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

int n;
long long acc[NMAX], sol;
vector<int> G[NMAX];

inline bool cmp(int x, int y)
{
    return acc[x] > acc[y];
}

void dfs1(int nod)
{
    for (int i = 0; i < G[nod].size(); i++)
    {
        dfs1(G[nod][i]);
        acc[nod] += acc[G[nod][i]];
    }

    sort (G[nod].begin(), G[nod].end(), cmp);
}

void dfs2(int nod)
{
    for (int i = 0; i < G[nod].size(); i++)
    {
        sol += (i+1) * acc[G[nod][i]];
        dfs2(G[nod][i]);
    }
}

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++)
        fin >> acc[i];

    dfs1(1);
    sol += acc[1];
    dfs2(1);

    fout << sol;
    return 0;
}