Cod sursa(job #116930)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 19 decembrie 2007 20:40:18
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define fin  "dosare.in"
#define fout "dosare.out"

#define pb push_back
#define sz(c) (int)((c).size())
#define mp make_pair

const int Nmax = 16100;

int N;
long long cost[Nmax],nra[Nmax],ret;
vector <int> g[Nmax];

void readdata()
{
	int i,x;

	freopen(fin,"r",stdin);

	scanf("%d",&N);

	for ( i = 1 ; i < N ; ++i )
	{
		scanf("%d",&x);
		g[x].pb(i+1);
	}


	for ( i = 1 ; i <= N ; ++i )
	{
		scanf("%lld",&cost[i]);
		nra[i]=cost[i];
	}
}

void df1(int x)
{
	int i;

	for ( i = 0 ; i < sz(g[x]) ; ++i )
	{
		df1(g[x][i]);
		cost[x] += cost[ g[x][i] ];
	}
}

void df2(int x,long long c)
{
	int i;
	vector < pair <int,int> > v;

	++c;

	ret = ret + (long long) nra[x] * c;

	v.clear();

	for ( i = 0 ; i < sz(g[x]) ; ++i )
		v.pb( mp( cost[ g[x][i] ] , g[x][i] ) );	
	
	sort(v.rbegin(),v.rend());

	for ( i = 0 ; i < sz(v); ++i )
		df2(v[i].second,c+i);
}

void solve()
{
	df1(1);
	df2(1,0);

	freopen(fout,"w",stdout);
	printf("%lld\n",ret);
}

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