Cod sursa(job #1382910)

Utilizator loturiLoturi super ruperi loturi Data 9 martie 2015 18:21:21
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define Nmax 20005

using namespace std;

long long cost,d[Nmax];
int poz[Nmax];

vector <int> L[Nmax];

struct el
{
    long long val;
    int poz;
    bool operator <(const el A) const
    {
        return val>A.val;
    }
} v[Nmax];

inline void Dfs(int nod)
{
    int len,i;
    el w;
    vector <int> ::iterator it;
    for(it=L[nod].begin();it!=L[nod].end();++it)
    {
        Dfs(*it);
        d[nod]+=d[*it];
    }
    len=0;
    for(it=L[nod].begin();it!=L[nod].end();++it)
    {
        w.poz=*it; w.val=d[*it]; v[++len]=w;
    }
    sort(v+1,v+len+1);
    for(i=1;i<=len;++i)
    {
        poz[v[i].poz]=i;
        cost+=d[v[i].poz]*(i-1);
    }
    cost+=d[nod];
}

int main()
{
    int i,n,x;
    freopen ("dosare.in","r",stdin);
    freopen ("dosare.out","w",stdout);
    scanf("%d", &n);
    for(i=2;i<=n;++i)
    {
        scanf("%d", &x);
        L[x].push_back(i);
    }
    for(i=1;i<=n;++i) scanf("%lld", &d[i]);
    Dfs(1);
    printf("%lld\n", cost);
    return 0;
}