Cod sursa(job #718375)

Utilizator Catah15Catalin Haidau Catah15 Data 20 martie 2012 18:52:12
Problema Dosare Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>

using namespace std;

#define maxN 16010
#define PB push_back
#define int64 long long

int tata[maxN], nrA[maxN];
int64 A[maxN], Cost[maxN], ans;
vector <int> list[maxN];


inline int cmp (int i, int j)
{
	return A[i] > A[j];
}


void DFS (int nod)
{
	A[nod] = nrA[nod];
	for (unsigned int i = 0; i < list[nod].size(); ++ i)
		DFS (list[nod][i]), A[nod] += A[list[nod][i]];
	sort (list[nod].begin(), list[nod].end(), cmp);
}


void DFS2 (int nod)
{
	for (unsigned int i = 0; i < list[nod].size(); ++ i)
	{
		int nod2 = list[nod][i];
		
		Cost[nod2] = (int64) nrA[nod2] * (int64) (Cost[nod] + i + 1);
		ans += Cost[nod2];
		
		DFS2 (nod2);
	}
}


int main()
{
	freopen ("dosare.in", "r", stdin);
	freopen ("dosare.out", "w", stdout);
	
	int N;
	
	scanf ("%d", &N);
	
	for (int i = 2; i <= N; ++ i)
	{
		scanf ("%d", &tata[i]);
		list[tata[i]].PB (i);
	}
	
	for (int i = 1; i <= N; ++ i) scanf ("%d", &nrA[i]);
	Cost[1] = nrA[1];
	
	DFS (1);
	DFS2 (1);
	
	printf ("%lld", ans + Cost[1]);
	
	return 0;
}