Cod sursa(job #116675)

Utilizator wefgefAndrei Grigorean wefgef Data 19 decembrie 2007 11:22:25
Problema Dosare Scor Ascuns
Compilator cpp Status done
Runda Marime 1.83 kb
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <functional>
#include <cassert>

using namespace std;

typedef long long LL;

const int MAXN = 16024;
int A[MAXN];
vector<int> adj[MAXN];

//pair<LL, LL> go(int n, int paps) {
//	vector<pair<LL, LL> > vp;
//	for (vector<int>::iterator it = adj[n].begin(); it != adj[n].end(); ++it) {
//		if (paps == *it) continue;
//		vp.push_back(go(*it, n));
//	}
//
//	sort(vp.begin(), vp.end(), greater<pair<LL, LL> >());
//
//	//int S = vp.size();
//	//for (int step = 0; step < S; ++step) {
//	//	bool ok = false;
//	//	for (int i = 0; i+1 < S; ++i) {
//	//		if (vp[i] < vp[i+1]) {
//	//			swap(vp[i], vp[i+1]);
//	//			ok = true;
//	//		}
//	//	}
//	//	if (!ok) break;
//	//}
//
//	LL num = A[n], cost = A[n];
//	for (int i = 0; i < vp.size(); ++i) cost += vp[i].second + vp[i].first * (i+1), num += vp[i].first;
//	return make_pair(num, cost);
//}

pair<LL, LL> go1(int n, int paps) {
	vector<pair<LL, LL> > vp;
	for (vector<int>::iterator it = adj[n].begin(); it != adj[n].end(); ++it) {
		if (paps == *it) continue;
		vp.push_back(go1(*it, n));
	}

	sort(vp.begin(), vp.end(), greater<pair<LL, LL> >());

	LL num = A[n], cost = A[n];
	for (int i = 0; i < vp.size(); ++i) cost += vp[i].first + vp[i].second * (i+1), num += vp[i].second;
	return make_pair(cost, num);
}

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

	int N;
	scanf("%d", &N);
	assert(1 <= N && N <= 16000);

	for (int i = 1; i < N; ++i) {
		int paps;
		scanf("%d", &paps);
		assert(1 <= paps && paps <= N);
		adj[paps-1].push_back(i);
	}
	for (int i = 0; i < N; ++i) {
		scanf("%d", &A[i]);
		assert(A[i] >= 0 && A[i] <= 1000000);
	}

	pair<LL, LL> res = go1(0, -1);
	printf("%lld\n", res.first);

	return 0;
}