Cod sursa(job #1082564)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 14 ianuarie 2014 19:33:51
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define NMAX 16007
#define LL long long

using namespace std;

vector< int > v[NMAX];
LL D[NMAX];
LL Ans;
int n;

inline bool Cmp(int a, int b){
    return D[a] > D[b];
}

inline long long Dfs1(int Nod){
    for(vector< int >::iterator it = v[Nod].begin(); it != v[Nod].end(); ++it){
        Dfs1(*it);
        D[Nod] += D[*it];
    }
    sort(v[Nod].begin(), v[Nod].end(), Cmp);
    return (LL)D[1];
}

inline long long Dfs2(int Nod){
    int i = 1;
    for(vector< int >::iterator it = v[Nod].begin(); it != v[Nod].end(); ++it, ++i){
        Dfs2(*it);
        Ans += (LL)i * (LL)D[*it];
    }
    return Ans;
}

int main(){
    freopen("dosare.in", "r", stdin);
    freopen("dosare.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 2; i <= n; ++i){
        int b = 0;
        scanf("%d", &b);
        v[b].push_back(i);
    }
    for(int i = 1; i <= n; ++i)
        scanf("%lld", &D[i]);
    Ans = Dfs1(1);
    printf("%lld", Dfs2(1));
}