Cod sursa(job #221508)

Utilizator alexeiIacob Radu alexei Data 16 noiembrie 2008 18:32:36
Problema Dosare Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define NMAX 16024
vector< int >Q[NMAX];

long long T[NMAX],S[NMAX],C[NMAX];

void DFT(const int nod)
{
     vector< int >::iterator it;
     
     T[nod]=S[nod];
     for(it=Q[nod].begin(); it!=Q[nod].end(); ++it)
     {
                            DFT(*it);
                            T[nod]+=T[*it];                
     }     
}

inline int cmp(const int p1,const int p2)
{
       return C[ p1 ]>C[ p2 ];
}

long long solve(const int nod)
{
     vector< int >::iterator it;
     
     long long ANS=0;
     
     for(it=Q[nod].begin(); it!=Q[nod].end(); ++it)
                     ANS+=solve( *it );
                
     sort( Q[nod].begin(), Q[nod].end(), cmp );                
     
     int prec=1;
     for(it=Q[nod].begin(); it!=Q[nod].end(); ++it)
     {
                 ANS+=T[*it]*prec++;             
     }
     
     C[nod]=ANS;
     return ANS;
}

int main()
{
    freopen("dosare.in","r",stdin);
    freopen("dosare.out","w",stdout);
    
    int N;
    scanf("%d",&N);
    
    int i,a1;
    for(i=1; i<N; ++i)
    {
             scanf("%d",&a1);
             Q[a1].push_back(i+1);
    }
    
    long long ST=0;
    for(i=1; i<=N; ++i){
             scanf("%lld",&S[i]);
             ST+=S[i];
    }  
    DFT( 1 );
    printf("%lld\n",solve(1)+ST);
    
    return 0;
}