Cod sursa(job #128239)

Utilizator a7893Nae Mihai a7893 Data 26 ianuarie 2008 18:33:05
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<stdio.h>
#include<stdlib.h>
#define N 16001
int n,v[N],nra[N],*a[N],nr[N];
void read()
{
	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",&nra[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;
}
void df(int x)
{
	int i,y;
	v[x]=nra[x];
	for(i=1;i<=a[x][0];i++)
	{
		y=a[x][i];
		df(y);
		v[x]+=v[y];
	}
}
int compare(const void *a,const void *b)
{
	int *aa=(int*)a,*bb=(int*)b;
	return v[*bb]-v[*aa];
}
void solve()
{
	int i;
	for(i=1;i<=n;i++)
		df(i);
	/*for(i=1;i<=n;i++)
		printf("%d ",v[i]);*/
	for(i=1;i<=n;i++)
		qsort(a[i]+1,a[i][0],sizeof(a[i][1]),compare);
}
void calcul(int x,int oper)
{
	v[x]=oper;
	for(int i=1;i<=a[x][0];++i){
		int y=a[x][i];
		calcul(y,oper+i);
	}
}
long long rez()
{
	calcul(1,1);
	long long i,s=0;
	for(i=1;i<=n;i++)
		s+=nra[i]*v[i];
	return s;
}
int main()
{
	freopen("dosare.in","r",stdin);
	freopen("dosare.out","w",stdout);
	read();
	solve();
	printf("%lld\n",rez());
	return 0;
}