Cod sursa(job #432446)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 2 aprilie 2010 13:08:53
Problema Dosare Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define IN "dosare.in"
#define OUT "dosare.out"
#define Lg 16010

using namespace std;

vector <int> V[Lg];
int grad[Lg];
int fii[Lg];
int ap[Lg];
long rez ,*aux, N, x;

void citire()
{
    scanf ("%ld",&N);
    for (int i=2;i<=N;i++)
    {
        scanf ("%ld",&x);
        V[x].push_back(i);
        grad[x]++;
    }

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

void df(int nod)
{
    fii[nod]=1;
    for (int i=0;i<grad[nod];i++)
    {
        df(V[nod][i]);
        fii[nod]+=fii[V[nod][i]];
    }

    aux = new long (fii[nod]+1);

    for (int i=0;i<grad[nod];i++)
    {
        ap[nod]+=ap[V[nod][i]];
        aux[i]=ap[V[nod][i]];
    }
    sort(aux,aux+grad[nod]);
    rez+=ap[nod];

    for (int i=grad[nod]-1;i>=0;i--)
        rez+=(grad[nod]-1-i)*aux[i];
}

int main ()
{
    freopen (IN ,"r", stdin);
    freopen (OUT ,"w", stdout);

    citire();
    df(1);
    printf("%ld\n",rez);

    return 0;
}