Cod sursa(job #432451)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 2 aprilie 2010 13:12:25
Problema Dosare Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 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];
long long  ap[Lg];
long long rez , N, x;

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

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

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

    long long *aux;
    aux=new long long (grad[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("%lld\n",rez);

    return 0;
}