Cod sursa(job #431779)

Utilizator Mishu91Andrei Misarca Mishu91 Data 1 aprilie 2010 13:34:09
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <vector>

using namespace std;

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

const int MAX_N = 16005;

ifstream fin ("dosare.in");
ofstream fout ("dosare.out");

int N;
vector <int> G[MAX_N];
long long Sol, V[MAX_N];

void dfs(int nod)
{
	foreach(G[nod])
		dfs(*it);

	long long aux[MAX_N], nr = 0;
	foreach(G[nod])
	{
		V[nod] += V[*it];
		aux[nr++] = V[*it];
	}

	sort(aux, aux+nr, greater <int> ());

	Sol += V[nod];
	for(int i = 0; i < nr; ++i)
		Sol += i*aux[i];
}

int main()
{
	fin >> N;

	for(int i = 2; i <= N; ++i)
	{
		int x;
		fin >> x;
		G[x].push_back(i);
	}

	for(int i = 1; i <= N; ++i)
		fin >> V[i];

	dfs(1);

	fout << Sol;
}