Cod sursa(job #1705224)

Utilizator sucureiSucureiRobert sucurei Data 20 mai 2016 08:26:41
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

#define sh short int
#define pb push_back
#define ll long long
#define NMAX 16005
sh N;
ll rez,sum[NMAX];
vector<sh>a[NMAX];
bool cmp(const sh &i, const sh &j)
{
    return sum[i]>sum[j];
}

void df(sh n)
{
    size_t g=a[n].size();
    for (size_t i=0; i<g; ++i)
    {

        df(a[n][i]);
        sum[n]+=sum[a[n][i]];
    }
    sort(a[n].begin(),a[n].end(),cmp);
}

void df1(sh n)
{
    size_t g=a[n].size();
    for (size_t i=0; i<g; ++i)
    {
        df1(a[n][i]);
        rez+=(i+1)*sum[a[n][i]];
    }
}

int main()
{
    freopen("dosare.in","r",stdin);
    freopen("dosare.out","w",stdout);
    scanf("%hd",&N);
    for (sh i=2; i<=N; ++i)
    {
        sh x;
        scanf("%hd",&x);
        a[x].pb(i);
    }
    for (int i=1; i<=N; ++i)
        scanf("%lld",&sum[i]);
    df(1);
    df1(1);
    printf("%lld",rez+sum[1]);
    return 0;
}