Cod sursa(job #118607)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 26 decembrie 2007 23:19:00
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define maxn 16010
#define ll long long

int n;
vector <int> a[maxn];
int f[maxn],g[maxn];
ll c[maxn],d[maxn],v[maxn];

int cmp(int x,int y)
{
    return x>y;
}

void DFS(int nod)
{
    int i;
    
    d[nod] = f[nod];
    
    for (i=0;i<g[nod];i++)
    {
        DFS(a[nod][i]);
        d[nod] += d[a[nod][i]];
        c[nod] += c[a[nod][i]];
    }
    
    for (i=0;i<g[nod];i++) v[i]=d[a[nod][i]];
    c[nod] += d[nod];
    
    sort(v,v+g[nod],cmp);   
    
    for (i=0;i<g[nod];i++) c[nod] += 1LL*i*v[i]; 
}

int main()
{
    freopen("dosare.in","r",stdin);
    freopen("dosare.out","w",stdout);
    
    scanf("%d ",&n);
    
    int i,x;
    
    for (i=2;i<=n;i++)
    {
        scanf("%d ",&x);
        a[x].push_back(i);
    }
    
    for (i=1;i<=n;i++) scanf("%d ",&f[i]);
    
    for (i=1;i<=n;i++) g[i]=a[i].size();
    
    DFS(1);
    
    printf("%lld\n",c[1]);
    
    return 0;
}