Cod sursa(job #522109)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 14 ianuarie 2011 13:23:45
Problema Dosare Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=16003;
int n,d[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("%d",&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;
}
int dfsp(int nod)
{
    int 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("%d",dfsp(1)+d[1]);
}
int main()
{
    read();
    df(1);
    solve();
    return 0;
}