Cod sursa(job #2012178)

Utilizator refugiatBoni Daniel Stefan refugiat Data 18 august 2017 08:41:49
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream si("dosare.in");
ofstream so("dosare.out");

const int MAXN=16000;
vector<int> g[1+MAXN];
long long ans,c[1+MAXN];

void dfs(int nod)
{
    vector<long long> fii;
    for(auto &fiu:g[nod])
    {
        dfs(fiu);
        c[nod]+=c[fiu];
        fii.push_back(c[fiu]);
    }
    sort(fii.begin(),fii.end());
    ans+=c[nod];
    for(int i=fii.size()-1;i>=0;i--)
        ans=ans+1LL*(fii.size()-i-1)*fii[i];
}

int main()
{
    int n;
    si>>n;
    for(int i=2;i<=n;i++)
    {
        int x;
        si>>x;
        g[x].push_back(i);
    }
    for (int i=1;i<=n;i++)
        si>>c[i];
    dfs(1);
    so<<ans;
    return 0;
}