Cod sursa(job #208376)

Utilizator webspiderDumitru Bogdan webspider Data 16 septembrie 2008 00:12:52
Problema Dosare Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <vector>

using namespace std;

const int maxN = 16001;

int N;
int W[ maxN ];
int P[ maxN ];
long long C[ maxN ];
vector<int> fii[ maxN ];

int cmpf( const int X, const int Y ) {
    return ( W[ X ] > W[ Y ] );
}

void DFS( int nod ) {
    vector<int>::iterator it;
    for ( it = fii[ nod ].begin(); it != fii[nod].end(); it++ ) {
        DFS( *it );
    }
    sort( fii[ nod ].begin(), fii[ nod ].end(), cmpf );
    int i = 0;
    for ( it = fii[ nod ].begin(); it != fii[nod].end(); it++, i++ ) {
        //printf("C[%d] adaugam %d (%d)\n", nod, *it, C[*it]+W[*it]*i);
        C[ nod ] += C[ *it ] + W[ *it ]*i;
        W[ nod ] += W[ *it ];
    }
    C[ nod ] += W[ nod ];
    //printf("%d -> (%d, %d)\n", nod, W[nod], C[nod] );
}

int main() {
#ifndef PC_COMPILE
    freopen("dosare.in","r",stdin);
    freopen("dosare.out","w",stdout);
#else
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif

    scanf("%d\n", &N );

    for ( int i = 2; i <= N; i++ ) {
        scanf("%d\n", &P[i]);
        fii[ P[i] ].push_back( i );
    }
    for ( int i = 1; i <= N; i++ ) {
        scanf("%d\n", &W[i] );
    }

    DFS( 1 );

    printf("%lld\n", C[1] );

    return 0;
}