Cod sursa(job #2106179)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 15 ianuarie 2018 11:09:03
Problema Dosare Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<bits/stdc++.h>
#define maxN 100005
using namespace std;
int w[maxN];
int dp[maxN],n,x;
vector<int> v[maxN];
inline bool cmp(int a,int b)
{
    return w[a]>w[b];
}
int cost[maxN];
inline void dfs(int nod)
{
    dp[nod]=0;
    w[nod]=cost[nod];
    for(auto it:v[nod])
    {
        dfs(it);
        w[nod]+=w[it];
    }

    if(!v[nod].empty())
    {
        sort(v[nod].begin(),v[nod].end(),cmp);
        for(int i=0;i<(int)v[nod].size();i++)
        {
            dp[nod]=dp[nod]+i*w[v[nod][i]]+dp[v[nod][i]];
        }
    }
    dp[nod]+=w[nod];
}
int main()
{
    freopen("dosare.in","r",stdin);
    freopen("dosare.out","w",stdout);

    scanf("%d",&n);


    for(int i=2;i<=n;i++)
    {
        scanf("%d",&x);
        v[x].push_back(i);
    }

    for(int i=1;i<=n;i++)
        scanf("%d",&cost[i]);

    dfs(1);

    printf("%d\n",dp[1]);
    return 0;
}