Cod sursa(job #1775089)

Utilizator LucianTLucian Trepteanu LucianT Data 9 octombrie 2016 20:20:04
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
#define maxN 16005
using namespace std;
vector<int>v[maxN];
long long sol,cost[maxN];
int n,i,j,x;
void dfs(int nod)
{
    vector<long long>soncost;
    for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
        dfs(*it),
        cost[nod]+=cost[*it],
        soncost.push_back(cost[*it]);
    sort(soncost.begin(),soncost.end());
    sol+=cost[nod];
    for(int i=0;i<soncost.size();i++)
        sol+=1LL*(soncost.size()-1-i)*soncost[i];
}
int main()
{
    freopen("dosare.in","r",stdin);
    freopen("dosare.out","w",stdout);
    scanf("%d",&n);
    for(i=2;i<=n;i++)
        scanf("%d",&x),
        v[x].push_back(i);
    for(i=1;i<=n;i++)
        scanf("%lld",&cost[i]);
    dfs(1);
    printf("%lld",sol);
    return 0;
}