Cod sursa(job #2107213)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 16 ianuarie 2018 20:50:06
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define VAL 16005

using namespace std;

ifstream fin("dosare.in");
ofstream fout("dosare.out");

int N, i, j, A;
long long ap[VAL], stram[VAL];
long long dpsons[VAL];
vector <int> G[VAL];

void DFS(int nod)
{
    vector <int> :: iterator it;
    vector <int> V;
    int nr=0;
    stram[nod]=ap[nod];
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        DFS(*it);
        dpsons[nod]+=dpsons[*it];
        stram[nod]+=stram[*it];
        V.push_back(stram[*it]);
    }
    sort(V.begin(), V.end());
    nr=G[nod].size();
    for (it=V.begin(); it!=V.end(); it++)
    {
        dpsons[nod]+=1LL*nr*(*it);
        nr--;
    }
}

int main()
{
    fin >> N;
    for (i=2; i<=N; i++)
    {
        fin >> A;
        G[A].push_back(i);
    }
    for (i=1; i<=N; i++)
      fin >> ap[i];
    DFS(1);
    fout << dpsons[1]+stram[1] << '\n';
    fin.close();
    fout.close();
    return 0;
}