Cod sursa(job #372039)

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

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

void calc(int x)
{
	int 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(int x)
{

	int  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);
	int 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("%d\n",sol);
	return 0;
}