Cod sursa(job #1767408)

Utilizator TibixbAndrei Tiberiu Tibixb Data 28 septembrie 2016 23:09:03
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>
#define NMAX 16005
using namespace std;
vector<int> G[NMAX];
long long n, i, x, val[NMAX], na[NMAX], d[NMAX], fiu[NMAX];
ifstream cin("dosare.in");
ofstream cout("dosare.out");
bool cmp(int x, int y)
{
    return na[x] > na[y];
}
void dfs(int nod)
{
    if(G[nod].size() == 0)
    {
        d[nod] = val[nod];
        na[nod] = val[nod];
        return ;
    }
    //vector<int> fiu;
    int fiu[NMAX];
    na[nod] = val[nod];
    for(int i = 0; i < G[nod].size(); i++)
    {
        dfs(G[nod][i]);
        //fiu.push_back(G[nod][i]);
        fiu[i + 1] = G[nod][i];
        na[nod] += na[G[nod][i]];
    }
    //sort(fiu.begin(), fiu.end(), cmp);
    sort(fiu + 1, fiu + G[nod].size() + 1, cmp);
    d[nod] = na[nod];
    for(int i = 1; i <= G[nod].size(); i++)
    {
        d[nod] += d[fiu[i]] + (i - 1) * na[fiu[i]];
    }
}
int main()
{
    cin >> n;
    for(int i = 2; i <= n; i++)
    {
        cin >> x;
        G[x].push_back(i);
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> val[i];
    }
    dfs(1);
    cout << d[1];
    return 0;
}