Cod sursa(job #206747)

Utilizator mariusdrgdragus marius mariusdrg Data 9 septembrie 2008 11:53:19
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back

using namespace std;

const int maxn = 17000;

vector<long long> S,VECT[maxn];
long long N,VAL[maxn],VER[maxn];


void dfs(int i)
{
	VER[i] = 1;
	for(vector <long long> :: iterator it = VECT[i].begin();it != VECT[i].end(); ++it)
		if (!VER[*it])
		{
			dfs(*it);
			VAL[i] += VAL[*it];
		}
}

int main()
{
	freopen("dosare.in","r",stdin);
	freopen("dosare.out","w",stdout);
	scanf("%d\n",&N);
	for(int i = 2;i <= N; ++i)
	{
		int k;
		scanf("%d",&k);
		VECT[k].pb(i);
	}
	for(int i = 1;i <= N; ++i)
	{
		scanf("%d\n",&VAL[i]);	
	}
	dfs(1);
	long long sol = 0;
	for(int i = 1;i <= N; ++i)
	{
		for(vector<long long> :: iterator it = VECT[i].begin();it != VECT[i].end(); ++it)
		{
			S.pb(VAL[*it]);	
		}
		sort(S.begin(),S.end());
		for(int j = S.size() - 1,cnt = 1;j >= 0;--j,cnt++)
		{
			sol += S[j] * cnt;
		}
		S.clear();
	}
	sol += VAL[1];
	printf("%lld\n",sol);
	return 0;
}