Cod sursa(job #194139)

Utilizator ProtomanAndrei Purice Protoman Data 8 iunie 2008 15:48:28
Problema Dosare Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <algorithm>
#define mx 16010

using namespace std;

struct nod
{
	long nr;
	nod *ua;
} *l[mx];
long n;
long a[mx],d[mx],apel[mx];

inline bool cmp(const long &a,const long &b)
{
	return apel[a]>apel[b];
}

void aranj(long nd)
{
	nod *p,*s,*el;
	long i,j;
	p=l[nd];
	el=0;
	while (p)
	{
		l[nd]=p;
		p=l[nd]->ua;
		aranj(l[nd]->nr);
		s=new nod;
		s->nr=l[nd]->nr;
		s->ua=el;
		el=s;
		delete(l[nd]);
	}
	s=el;
	i=0;
	while (s)
	{
		el=s;
		s=el->ua;
		a[i++]=el->nr;
		delete(el);
	}
	j=i;
	sort(a,a+j,cmp);
	for (int i=0; i<j; i++)
	{
		d[nd]=d[nd]+(i+1)*apel[a[i]]+d[a[i]];
		apel[nd]=apel[nd]+apel[a[i]];
	}
}

void clad(long t, long f)
{
	nod *p;
	p=new nod;
	p->nr=f;
	p->ua=l[t];
	l[t]=p;
}

int main()
{
	freopen("dosare.in","r",stdin);
	freopen("dosare.out","w",stdout);
	scanf("%ld",&n);
	long t=0;
	for (int i=1; i<n; i++)
	{
		scanf("%ld",&t);
		clad(t,i+1);
	}
	for (int i=1; i<=n; i++)
	{
		scanf("%ld",&d[i]);
		apel[i]=d[i];
	}
	aranj(1);
	printf("%ld",d[1]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}