Cod sursa(job #978581)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 29 iulie 2013 01:05:18
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define fin  "dosare.in"
#define fout "dosare.out"
 
#define pb push_back
#define sz(c) (int)((c).size())
#define mp make_pair
 
const int Nmax = 16100;
 
int N;
long long cost[Nmax],nra[Nmax],ret;
vector <int> g[Nmax];
 
void readdata()
{
    int i,x;
 
    freopen(fin,"r",stdin);
 
    scanf("%d",&N);
 
    for ( i = 1 ; i < N ; ++i )
    {
        scanf("%d",&x);
        g[x].pb(i+1);
    }
 
 
    for ( i = 1 ; i <= N ; ++i )
    {
        scanf("%lld",&cost[i]);
        nra[i]=cost[i];
    }
}
 
void df1(int x)
{
    int i;
 
    for ( i = 0 ; i < sz(g[x]) ; ++i )
    {
        df1(g[x][i]);
        cost[x] += cost[ g[x][i] ];
    }
}
 
void df2(int x,long long c)
{
    int i;
    vector < pair <int,int> > v;
 
    ++c;
 
    ret = ret + (long long) nra[x] * c;
 
    v.clear();
 
    for ( i = 0 ; i < sz(g[x]) ; ++i )
        v.pb( mp( cost[ g[x][i] ] , g[x][i] ) );    
     
    sort(v.rbegin(),v.rend());
 
    for ( i = 0 ; i < sz(v); ++i )
        df2(v[i].second,c+i);
}
 
void solve()
{
    df1(1);
    df2(1,0);
 
    freopen(fout,"w",stdout);
    printf("%lld\n",ret);
}
 
int main()
{
    readdata();
    solve();
    return 0;
}