Cod sursa(job #118225)

Utilizator megabyteBarsan Paul megabyte Data 23 decembrie 2007 20:02:19
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define INF "dosare.in"
#define OUF "dosare.out"
#define NMAX 16002
#define pb push_back
#define sz(arg) arg.size()

using namespace std;

struct nod
{
	int i,sub;
};
int v[NMAX],vsub[NMAX],n;
vector<nod> a[NMAX];
char viz[NMAX]={0};

bool cmp(nod a,nod b) { return (a.sub>b.sub);}

void dfinit(int nd)
{
	int i,nb;
	viz[nd]=1;
	vsub[nd]=v[nd];
	for(i=0;i<sz(a[nd]);++i)
	if(!viz[a[nd][i].i])
	{
		nb=a[nd][i].i;
		dfinit(nb);
		vsub[nd]+=vsub[nb];
		a[nd][i].sub=vsub[nb];
	}
	sort(a[nd].begin(),a[nd].end(),cmp);
}

void dfrez(int nd,int acost)
{
	int i,nb;
	viz[nd]=1;
//	printf("%d ",nd);
	vsub[nd]=acost;
	for(i=0;i<sz(a[nd]);++i)
	if(!viz[a[nd][i].i])
	{
		nb=a[nd][i].i;
		dfrez(nb,acost+i+1);
	}
}


int main()
{
	FILE *in,*out;
	int i,x;
	nod alfa;
	long long sol,aux;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%d",&n);
	for(i=2;i<=n;++i)
	{
		fscanf(in,"%d",&x);
		alfa.i=i;alfa.sub=0;
		a[x].pb(alfa);
	}

	for(i=1;i<=n;++i) fscanf(in,"%d",v+i);
	dfinit(1);
	
	memset(viz,0,NMAX);
	dfrez(1,1);
	sol=0;
//	printf("\n");
	for(i=1;i<=n;++i) 
	{
//		printf("%d ",vsub[i]);
		aux=vsub[i];
		aux*=v[i];
		sol+=aux;
	}

	fprintf(out,"%lld",sol);
	fclose(in);fclose(out);
	return 0;
}