Cod sursa(job #116872)

Utilizator filipbFilip Cristian Buruiana filipb Data 19 decembrie 2007 19:13:09
Problema Dosare Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define NMax 16005

int N, A[NMax], C[NMax], SUM[NMax];
vector<short int> G[NMax];

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

void df(int nod)
{
    int i, sz;

    for (sz = G[nod].size(), i = 0, SUM[nod] = A[nod]; i < sz; i++)
    {
        df(G[nod][i]);
        SUM[nod] += SUM[G[nod][i]];
    }

    C[nod] = A[nod];
    if (!sz) return ;

    sort(G[nod].begin(), G[nod].end(), cmp);    
    for (sz = G[nod].size(), i = 0; i < sz; i++)
        C[nod] += C[G[nod][i]] + (i+1) * SUM[G[nod][i]];
}

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

    scanf("%d", &N);
    for (i = 2; i <= N; i++)
    {
        scanf("%d", &u);
        G[u].push_back(i);
    }
    for (i = 1; i <= N; i++)
        scanf("%d", &A[i]);

    df(1);

    printf("%d\n", C[1]);

    return 0;
}