Cod sursa(job #2022792)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 17 septembrie 2017 12:11:56
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>

using namespace std;

#define maxN 16010
#define PB push_back
#define int64 long long

int tata[maxN], nrA[maxN];
int64 A[maxN], Cost[maxN], ans;
vector <int> list[maxN];


inline int cmp (int i, int j)
{
    return A[i] > A[j];
}


void DFS (int nod)
{
    A[nod] = nrA[nod];
    for (unsigned int i = 0; i < list[nod].size(); ++ i)
        DFS (list[nod][i]), A[nod] += A[list[nod][i]];
    sort (list[nod].begin(), list[nod].end(), cmp);
}


void DFS2 (int nod)
{
    for (unsigned int i = 0; i < list[nod].size(); ++ i)
    {
        int nod2 = list[nod][i];

        Cost[nod2] = Cost[nod] + i + 1;
        ans += (int64) nrA[nod2] * (int64) (Cost[nod] + i + 1);

        DFS2 (nod2);
    }
}


int main()
{
    freopen ("dosare.in", "r", stdin);
    freopen ("dosare.out", "w", stdout);

    int N;

    scanf ("%d", &N);

    for (int i = 2; i <= N; ++ i)
    {
        scanf ("%d", &tata[i]);
        list[tata[i]].PB (i);
    }

    for (int i = 1; i <= N; ++ i) scanf ("%d", &nrA[i]);
    Cost[1] = 1;

    DFS (1);
    DFS2 (1);

    printf ("%lld", ans + nrA[1]);

    return 0;
}