Pagini recente » Cod sursa (job #2424227) | Cod sursa (job #1495880) | Cod sursa (job #779199) | Cod sursa (job #1075756) | Cod sursa (job #978612)
Cod sursa(job #978612)
#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;
}