Cod sursa(job #485044)

Utilizator nandoLicker Nandor nando Data 16 septembrie 2010 20:50:54
Problema Dosare Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 16010

typedef vector<int>::iterator iter;
vector< int> g[MAXN];
int n;
long long 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());
	int i = 0;
	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;
}