Cod sursa(job #119510)

Utilizator gcosminGheorghe Cosmin gcosmin Data 1 ianuarie 2008 17:20:03
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 16010
#define MP make_pair
#define LL long long

int N;

vector <int> leg[NMAX];
vector <pair<int, int> > jeg[NMAX];

int tata[NMAX];
int nr[NMAX];
LL sol[NMAX];

int cmp(pair<int, int> a, pair<int, int> b)
{
	return (a > b);
}

void solve(int x)
{
	sol[x] = nr[x];

	for (vector <int> :: iterator it = leg[x].begin(); it != leg[x].end(); ++it) {
		solve(*it);

		nr[x] += nr[*it];

		jeg[x].push_back(MP(nr[*it], *it));
	}

	sort(jeg[x].begin(), jeg[x].end(), cmp);

	int q = 0;
	for (vector <pair<int, int> > :: iterator it = jeg[x].begin(); it != jeg[x].end(); ++it) {
		q++;
		sol[x] += (LL) q * nr[it->second] + sol[it->second];
	}
}

int main()
{
	int i;

	freopen("dosare.in", "r", stdin);
	freopen("dosare.out", "w", stdout);

	scanf("%d", &N);

	for (i = 2; i <= N; i++) scanf("%d", &tata[i]);

	for (i = 1; i <= N; i++) scanf("%d", &nr[i]);

	for (i = 2; i <= N; i++) leg[tata[i]].push_back(i);

	solve(1);

	printf("%lld\n", sol[1]);

return 0;
}