Cod sursa(job #372040)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 8 decembrie 2009 12:34:18
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
long long n,sol,nr[16002],s[16002];
vector<long long> v[16002];

bool cmp(long long x, long long y)
{
	return x>y;
}

void calc(long long x)
{
	long long i,lim=v[x].size();
	for(i=0;i<lim;i++)
	{
		s[i]=nr[v[x][i]];
		nr[x]+=s[i];
	}
	sol+=nr[x];
	sort(s,s+lim,cmp);
	for(i=0;i<lim;i++)
		sol=sol+i*s[i];
}

void dfs(long long x)
{

	long long  i,lim=v[x].size();
	for(i=0;i<lim;i++)
		dfs(v[x][i]);
	calc(x);
}
int main()
{
	freopen("dosare.in","r",stdin);
	freopen("dosare.out","w",stdout);
	scanf("%d",&n);
	long long i,x;
	for(i=2;i<=n;i++)
	{
		scanf("%d",&x);
		v[x].push_back(i);
	}
	for(i=1;i<=n;i++)
		scanf("%d",&nr[i]);
	dfs(1);
	printf("%lld\n",sol);
	return 0;
}