Cod sursa(job #667078)

Utilizator nandoLicker Nandor nando Data 22 ianuarie 2012 16:39:18
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 16010
typedef long long int64;

typedef vector<int>::iterator iter;
vector< int> g[MAXN];
int n;
int64 a[MAXN], res = 0;

void dfs(int nod)
{
	vector<int> ord;
	for(iter it = g[nod].begin(); it != g[nod].end(); ++it){
		 dfs(*it);
		 a[nod] += a[*it];
		 ord.push_back(a[*it]);
	}

	res += a[nod];

	sort(ord.rbegin(), ord.rend());
	int64 i = 0LL;
	for(iter it = ord.begin(); it != ord.end(); ++it, ++i){
		res += i * (*it);
	}
}

int main()
{
	FILE* fin = fopen("dosare.in", "r");
	FILE* fout = fopen("dosare.out", "w");

	fscanf(fin, "%d\n", &n);
	for(int i = 2, x; i <= n; ++i){
		fscanf(fin, "%d ", &x);
		g[x].push_back(i);
	}

	for(int i = 1; i <= n; ++i){
		fscanf(fin, "%lld ", &a[i]);
	}

	dfs(1);
	fprintf(fout, "%lld\n", res);

	fclose(fin);
	fclose(fout);
	return 0;
}