Cod sursa(job #401290)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 22 februarie 2010 18:42:29
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

#define sh short int
#define pb push_back
#define ll long long
#define NMAX 16005
sh N;
ll rez,sum[NMAX];
vector<sh>a[NMAX];
bool cmp(const sh &i, const sh &j)
{
	return sum[i]>sum[j];
}

void df(sh n)
{
	size_t g=a[n].size();
	for (size_t i=0; i<g; ++i)
	{

		df(a[n][i]);
		sum[n]+=sum[a[n][i]];
	}
	sort(a[n].begin(),a[n].end(),cmp);
}

void df1(sh n)
{
	size_t g=a[n].size();
	for (size_t i=0; i<g; ++i)
	{
		df1(a[n][i]);
		rez+=(i+1)*sum[a[n][i]];
	}
}

int main()
{
	freopen("dosare.in","r",stdin);
	freopen("dosare.out","w",stdout);
	scanf("%hd",&N);
	for (sh i=2; i<=N; ++i)
	{
		sh x;
		scanf("%hd",&x);
		a[x].pb(i);
	}
	for (int i=1; i<=N; ++i)
		scanf("%lld",&sum[i]);
	df(1);
	df1(1);
	printf("%lld",rez+sum[1]);
	return 0;
}