Cod sursa(job #198320)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 10 iulie 2008 13:25:46
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
# include <stdio.h>
# include <vector>
# include <algorithm>

using namespace std;

# define FIN "dosare.in"
# define FOUT "dosare.out"
# define MAXN 16001
# define ll long long

vector <ll> H[MAXN];
ll A[MAXN];
ll P[MAXN];
ll s;
ll N,i,x;

    void parcurg(ll nod)
    {
        ll j,len;
        len = H[nod].size();
        for (j = 0; j < len; ++j)
          parcurg(H[nod][j]);
        
        for (j = 0; j < len; ++j)
          P[j+1] = A[H[nod][j]];
        
        sort(P+1,P+len+1);
        
        for (j = len; j >= 1; --j)
          {
              A[nod] +=P[j];
              s += (len - j + 1) * P[j];
          }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%lld",&N);
        for (i = 2; i <= N; ++i)
          {
               scanf("%lld",&x);
               H[x].push_back(i);
          }
        H[0].push_back(1);
        for (i = 1; i <= N; ++i)
          scanf("%lld",&A[i]);
        
        s = 0;
        parcurg(0);
        
        printf("%lld",s);
        
        return 0;
    }