Cod sursa(job #198164)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 9 iulie 2008 00:01:22
Problema Dosare Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 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 

using namespace std;
vector < vector<int> > a(N_MAX); 
int tata[N_MAX];
int prior[N_MAX]; 
int acces[N_MAX];
int total[N_MAX];
int stv[N_MAX];
bool marg[N_MAX];
int niv,N;

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

void see_for(int nod)
{
	nod = stv[nod];
	if(total[nod] !=-1)
		return;
	int suma=0,l=a[nod].size();
	FOR(i,0,l-1)
		if(total[ a[nod][i] ] == -1)
			return;
		else
			suma += total[ a[nod][i] ];
	total[nod] = suma + acces[nod];	
	if(tata[nod] != 0)
		stv[++niv] = tata[nod];
}

inline int comp (int x, int y)
{
	return total[x] > total[y];
}

void solve()
{
	niv=0;
	FOR(i,1,N)
		if(!marg[i])
			stv[++niv] = i;
	
	FOR(i,1,niv)
		see_for(i);
	
	FOR(i,1,N)
		sort(a[i].begin(),a[i].end() ,comp);
	
	FOR(i,1,N)
	{
		int l=a[i].size();
		FOR(j,0,l-1)
			prior[a[i][j]] = j+1;
	}
	niv=1;
	stv[1] = 1;
	total[1] = 1;
	
	FOR(i,1,niv)
	{
		int l=a[i].size();
		FOR(j,0,l-1)
		{
			int nod = a[i][j];
			stv[++niv] = nod;
			total[ nod ] = total[ tata[nod] ] + prior[nod];
		}
	}	
}

void print()
{
	ll suma=0;
	FOR(i,1,N)
		suma += (ll)acces[i] * total[i];
	printf("%lld\n",suma);
}	

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