Cod sursa(job #171704)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 4 aprilie 2008 20:57:42
Problema Dosare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define vv 16010

using namespace std;

vector <long long> w[vv];
long long a[vv],s,aux[vv];
int n;

void citire()
{
    freopen("dosare.in","r",stdin);
    scanf("%d", &n);
    int q;
    for (int i=1; i<n; i++)
    {
        scanf("%d", &q);
        w[--q].push_back(i);
    }
    for (int i=0; i<n; i++)
        scanf("%lld", &a[i]);
}

void dosar(long long e, long long q)
{
    for (vector <long long>::iterator it=w[e].begin(); it!=w[e].end(); it++)
        dosar(*it, q+1);
    for (vector <long long>::iterator it=w[e].begin(); it!=w[e].end(); it++)
        aux[it-w[e].begin()]=a[*it];
    sort(aux, aux+w[e].size());
    reverse(aux, aux+w[e].size());
    for (vector <long long>::iterator it=w[e].begin(); it!=w[e].end(); it++)
    {
        s+=(it-w[e].begin())*aux[it-w[e].begin()];
        a[e]+=aux[it-w[e].begin()];
    }
    s+=a[e];
}

int main()
{
    citire();
    dosar(0,1);
    freopen("dosar,out","w",stdout);
    printf("%lld\n", s);
    return 0;
}