Cod sursa(job #140732)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 22 februarie 2008 10:47:52
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

const int N_MAX = 16010;

vector <int> G[N_MAX];
int acc[N_MAX], niv[N_MAX], sub[N_MAX], dad[N_MAX];

void DF(int nod, int nivel)
{
	niv[nod] = nivel;
	sub[nod] = acc[nod];
		
	vector <int>::iterator it;
	for (it = G[nod].begin(); it != G[nod].end(); ++ it) {
		DF(*it, nivel + 1);
		sub[nod] += sub[*it];
	}
}

int cmp(int a, int b)
{
	return (sub[a] > sub[b]);
}

int sol[N_MAX], cat[N_MAX];

long long rez = 0;

void aranj(int nod)
{
	vector <int>::iterator it;
	sol[0] = 0;
	for (it = G[nod].begin(); it != G[nod].end(); ++ it) {
		sol[++ sol[0]] = *it;
	}

	sort(sol + 1, sol + sol[0] + 1, cmp);
	int i;
	for (i = 1; i <= sol[0]; i ++) {
		cat[sol[i]] = cat[dad[sol[i]]] + i;
		rez += (acc[sol[i]] * (cat[sol[i]]));
	}

	for (it = G[nod].begin(); it != G[nod].end(); ++ it) {
		aranj(*it);
	}
}


int main()
{
	freopen("dosare.in", "r", stdin);
#ifndef _SCREEN_
	freopen("dosare.out", "w", stdout);
#endif

	int N, i, x;
	scanf("%d\n", &N);
	for (i = 2; i <= N; i ++) {
		scanf("%d ", &x);
		G[x].push_back(i);
		dad[i] = x;
	}
	for (i = 1; i <= N; i ++) {
		scanf("%d ", &acc[i]);
	}

	DF(1, 1);
	cat[1] = 1;
	aranj(1);
	printf("%lld\n", rez + acc[1]);

	return 0;
}