Cod sursa(job #116685)

Utilizator wefgefAndrei Grigorean wefgef Data 19 decembrie 2007 12:06:30
Problema Dosare Scor Ascuns
Compilator cpp Status done
Runda Marime 0.84 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 16005

int N;
vector<int> con[MAXN];
int op[MAXN];

long long bst[MAXN], nrOp[MAXN];

inline int cmp( int a, int b ) { return nrOp[a] > nrOp[b]; }

void dfs( int k )
{
	vector<int> :: iterator it;

	bst[k] = nrOp[k] = op[k];
	for (it = con[k].begin(); it != con[k].end(); it++)
	{
		dfs(*it);
		nrOp[k] += nrOp[*it];
		bst[k] += bst[*it];
	}

	sort( con[k].begin(), con[k].end(), cmp );
	for (size_t a = 0; a < con[k].size(); a++)
		bst[k] += nrOp[ con[k][a] ] * (a + 1);
}

int main()
{
	freopen("dosare.in", "rt", stdin);
	freopen("dosare.out", "wt", stdout);

	scanf("%d", &N);
	for (int i = 2; i <= N; i++)
	{
		int p;
		scanf("%d", &p);
		con[p].push_back(i);
	}
	for (int i = 1; i <= N; i++)
		scanf("%d", op + i);
	dfs(1);
	printf("%lld\n", bst[1]);

	return 0;
}