Cod sursa(job #119529)

Utilizator andrei.12Andrei Parvu andrei.12 Data 1 ianuarie 2008 19:20:26
Problema Dosare Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<stdio.h>
#include<algorithm>
#define lg 16005

using namespace std;

int n, a, i, nr[lg], *v[lg];
long long vl[lg], ac[lg], act[lg];
int cmp(int a, int b){
	if (a != b)
		return (a > b);
	return 0;
}
void df(int nod, int str){
	int i;
	//fprintf(stderr, "%d\n", nod);
	if (!nr[nod]){
		vl[nod] = ac[nod];
		act[nod] = ac[nod];
		act[str] += act[nod];
		//fprintf(stderr, "pentru nodul %d valoarea este %d\n", nod, vl[nod]);
		return ;
	}
	
	int ind = 0, q[nr[nod]+1];
	for (i = 1; i <= nr[nod]; i ++)
		df(v[nod][i], nod);
	act[nod] += ac[nod];
	act[str] += act[nod];
	
	for (i = 1; i <= nr[nod]; i ++)
		q[++ind] = act[v[nod][i]];
	
	sort(q+1, q+ind+1, cmp);
	
	for (i = 1; i <= nr[nod]; i ++){
		vl[nod] += q[i]*i + vl[v[nod][i]];
		//fprintf(stderr, "%d ", i*q[i]);
	}
	vl[nod] += ac[nod];
	//fprintf(stderr, "\npentru nodul %d valoarea este %d\n", nod, vl[nod]);
}	
int main()
{
	freopen("dosare.in", "rt", stdin);
	freopen("dosare.out", "wt", stdout);
	
	scanf("%d", &n);
	
	for (i = 1; i < n; i ++){
		scanf("%d", &a);
		nr[a] ++;
		v[a] = (int*)realloc(v[a], (nr[a]+1)*sizeof(int));
		v[a][nr[a]] = i+1;
	}
	
	for (i = 1; i <= n; i ++)
		scanf("%lld", &ac[i]);
	
	df(1, 0);	
	
	printf("%lld\n", vl[1]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}