Cod sursa(job #194582)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 12 iunie 2008 09:31:22
Problema Dosare Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#include<stdlib.h>
#define N 1005
int n,v[N],s[N],*a[N],nr[N];
void funct(int x){
    int i,y;
    v[x]=s[x];
    for(i=1;i<=a[x][0];i++){
        y=a[x][i];
        funct(y);
        v[x]+=v[y];
    }
}
int comp(const void *a,const void *b){
    int *aa=(int*)a,*bb=(int*)b;
    return v[*bb]-v[*aa];
}
void solv(){
    int i;
    for(i=1;i<=n;i++)
        funct(i);
    for(i=1;i<=n;i++)
        qsort(a[i]+1,a[i][0],sizeof(a[i][1]),comp);
}
void calc(int x,int z){
    v[x]=z;
    for(int i=1;i<=a[x][0];++i){
        int y=a[x][i];
        calc(y,z+i);
    }
}
long long rez(){
    calc(1,1);
    long long i,x=0;
    for(i=1;i<=n;i++)
        x+=s[i]*v[i];
    return x;
}
int main(){
    freopen("dosare.in","r",stdin);
    freopen("dosare.out","w",stdout);
    int i;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        scanf("%d",&v[i]);
        ++nr[v[i]];
    }
    for(i=1;i<=n;i++)
        scanf("%d",&s[i]);
    for(i=1;i<=n;i++){
        a[i]=new int[nr[i]+1];
        a[i][0]=0;
    }
    for(i=2;i<=n;i++)
        a[v[i]][++a[v[i]][0]]=i;
    solv();
    printf("%lld\n",rez());
	fclose(stdin);
	fclose(stdout);
    return 0;
}