Cod sursa(job #198166)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 9 iulie 2008 00:51:41
Problema Dosare Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define IN "dosare.in"
#define OUT "dosare.out"
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define N_MAX 16001
#define pb push_back
#define ll long long 
#define sz size()  

using namespace std;
vector < vector<int> > a(N_MAX); 
int acces[N_MAX];
int total[N_MAX];
int N;
ll sol;

void scan()
{
	int x;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d", &N);
	FOR(i,1,N)
	{
		scanf("%d", &x);
		a[--x].pb(i);
	}	
	FOR(i,0,N)
		scanf("%d", &acces[i]);
}		

void DF(int nod,int cost)
{
	int l = a[nod].sz;
	FOR(j,0,l)
		DF(a[nod][j],cost+1);
	
	FOR(j,0,l)  
        total[j] = acces[ a[nod][j] ];  

	sort(total , total + l );  
    reverse(total , total + l ); 	
	
	FOR(j,0,l)  
		sol += (ll)j* total[j],
		acces[nod] += total[j];  
	
	sol += (ll)acces[nod];  
	
}

void solve()
{
	DF(0,1);
	printf("%lld ",sol);
}

int main()
{
	scan();
	solve();
	return 0;
}