Cod sursa(job #118195)

Utilizator raula_sanChis Raoul raula_san Data 23 decembrie 2007 15:50:09
Problema Dosare Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>

#define dim 16001

using namespace std;

vector <int> V[dim], O[dim];

vector < pair <int, int> > X;

int N;
int A[dim];

long long S;
long long Cnt[dim];

void read()
{
	freopen("dosare.in", "rt", stdin);
	
	int i, j;
	
	for(scanf("%d", &N), i=2; i<=N; ++i)
	{
		scanf("%d", &j);
		V[j].push_back(i);
	}
	
	for(i=1; i<=N; ++i)
		scanf("%d", A+i);
	
	fclose(stdin);
}

void df(int nod)
{
	int i, n;
	
	n = V[nod].size();
	
	for(i=0; i<n; ++i)
	{
		df(V[nod][i]);
		
		Cnt[nod] += Cnt[V[nod][i]];
		Cnt[nod] += A[V[nod][i]];
	}
	
	for(i=0; i<n; ++i)
		X.push_back(make_pair(Cnt[V[nod][i]], V[nod][i]));
		
	sort(X.begin(), X.end());
	
	for(i=n-1; i>=0; --i)
		O[nod].push_back(X[i].second);
		
	X.clear();
}

void count(int nod)
{	
	int i, n;
	
	n = O[nod].size();

	++ Cnt[nod];
	
	for(i=0; i<n; ++i)
	{
		Cnt[O[nod][i]] += Cnt[nod];
		Cnt[O[nod][i]] += i;
		
		count(O[nod][i]);
	}
}

void write()
{
	freopen("dosare.out", "wt", stdout);
	
	int i;
	
	for(i=1; i<=N; ++i)
		S += Cnt[i] * A[i];
		
	printf("%lld", S);
	
	fclose(stdout);
}

int main()
{
	read();
	df(1);
	memset(Cnt, 0, sizeof(Cnt));
	count(1);
	write();
	
	return 0;
}