Cod sursa(job #522110)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 14 ianuarie 2011 13:25:47
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const long long N=16003;
long long d[N];
int n;
vector<int> L[N];
void read()
{
    freopen("dosare.in","r",stdin);
    freopen("dosare.out","w",stdout);
    int x;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&x);
        L[x].push_back(i);
    }
    for(int i=1;i<=n;i++)
        scanf("%lld",&d[i]);
}
void df(int nod)
{
    for(vector<int>::iterator it=L[nod].begin();it!=L[nod].end();it++)
    {
        df(*it);
        d[nod]+=d[*it];
    }
}
bool comp(const int &a,const int &b)
{
    if(d[a]<d[b])
        return false;
    return true;
}
long long dfsp(int nod)
{
    long long q=-1,sc=0;
    for(vector<int>::iterator it=L[nod].begin();it!=L[nod].end();it++)
    {
        q++;
        sc+=dfsp(*it)+q*d[*it]+d[*it];
    }
    return sc;
}
void solve()
{
    for(int i=1;i<=n;i++)
        sort(L[i].begin(),L[i].end(),comp);
    printf("%lld",dfsp(1)+d[1]);
}
int main()
{
    read();
    df(1);
    solve();
    return 0;
}