Cod sursa(job #978612)

Utilizator superman_01Avramescu Cristian superman_01 Data 29 iulie 2013 11:46:03
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>

#define NMAX 16005

using namespace std;

ifstream f("dosare.in");
ofstream g("dosare.out");

long long Answer;
vector < int > G[NMAX];
long long N,cost[NMAX];
int acc[NMAX];
bool used[NMAX];
bool cmp ( int nod1 , int nod2 )
{
	return cost[nod1] > cost[nod2] ;
}

inline void FirstDepthFirstSearch ( int node , int level )
{
	used[node] = true ; 
	for( vector < int > ::iterator it= G[node].begin() ; it !=G[node].end() ; ++it)
		if( !used[*it]) 
		{
			FirstDepthFirstSearch( *it , level +1 );
			cost[node]+=cost[*it];
		}
	sort ( G[node].begin() , G[node].end() , cmp );
}
void SecondDepthFirstSearch ( int node )
{
	int level =  0 ;
	used[node] = true ;
	for( vector < int > ::iterator it= G[node].begin() ; it !=G[node].end() ; ++it)
		if( !used[*it]) 
		{
			Answer += ( long long )  (level +1 ) * cost[*it];
			++level ;
			SecondDepthFirstSearch ( *it );
		}
}

int main ( void )
{
	int i ,x  ;
	
	f>>N;
	for( int i(1) ; i < N ; ++i )
	{
		f>>x;
		G[x].push_back(i+1);
	}
	for( int i(1) ; i <= N ; ++i )
		f>>acc[i] , cost[i] = acc[i] ;
	FirstDepthFirstSearch( 1 , 1 );
	memset(used,0,sizeof(used));
	SecondDepthFirstSearch( 1 ) ;
	g<<Answer+cost[1]<<"\n";
	f.close();
	g.close();
	return 0;
}