Cod sursa(job #410341)

Utilizator lalasCont de teste lalas Data 4 martie 2010 11:53:03
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
#include<vector>
#include<algorithm>
const int maxn = 16005;
#define ll long long
using namespace std;

int i , j , a , n , v[maxn] , tot[maxn] ;
ll int res;
vector <int> G[maxn];

inline bool cmp (int x , int y ) {
	return ( tot[x] > tot[y] );
}

void DF( int node ) 
{
	int i;
	if( G[node].empty())  return;
	
	for( i = 0 ; i < G[node].size() ; ++i ){
		DF(G[node][i]),
		tot[node] += tot[G[node][i]];
	}
	
	sort( G[node].begin() , G[node].end() , cmp);
}

void DF2(int node , int depth , int dep)
{
	int i = 0 , act;
	
	res += 1LL * v[node] * ( depth + dep + 1 );
	
	for( i = 0 ; i < G[node].size() ; ++i ) {
		act = G[node][i];
		DF2( act , depth + 1 , i + dep);
}

}
	

int main()
{
	freopen("dosare.in","r",stdin);
	freopen("dosare.out","w",stdout);
	
	scanf("%d",&n);
	for( i = 2 ; i <= n ; ++i ) { 
		scanf("%d",&a);
		G[a].push_back(i);
	}
	
	for( i = 1 ; i <= n ; ++i )
		scanf("%d",&v[i]) , tot[i] = v[i];
	
	DF(1);
	DF2(1 , 0 , 0);
	
printf("%lld\n",res);
	
return 0;
}