Cod sursa(job #2030089)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 1 octombrie 2017 02:34:38
Problema Dosare Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define DIM 16002

using namespace std;

ifstream f("dosare.in");
ofstream g("dosare.out");

long long n, cost[DIM], t[DIM], cost2[DIM], cost3[DIM], cost4[DIM];

long long s;

vector <int> arb[DIM];

void Cost(int nod)
{
    for(int i = 0; i < arb[nod].size(); ++ i)
    {
        Cost(arb[nod][i]);
    }
    if(nod != 1)
    {
        cost[t[nod]] += cost[nod];
    }
}

int sol(int nod)
{
    for(int i = 0; i < arb[nod].size(); ++ i)
    {
        int nodc = arb[nod][i];
        cost2[nodc] = (cost4[nod] + i + 1) * cost3[nodc];
        cost4[nodc] = cost4[nod] + i + 1;
        sol(nodc);
    }
}

bool cmd(int a, int b)
{
    return cost[a] > cost[b];
}

int main()
{
    f>>n;
    for(int i = 2; i <= n; ++ i)
        f>>t[i];

    cost2[1] = 1;
    cost4[1] = 1;

    for(int i = 1; i <= n; ++ i)
    {
        f>>cost[i];
        cost3[i] = cost[i];
    }

    for(int i = 1; i <= n; ++ i)
    {
        arb[t[i]].push_back(i);
    }

    Cost(1);

    for(int i = 1; i <= n; ++ i)
        sort(arb[i].begin(), arb[i].end(), cmd);

    /*for(int i = 1; i <= n; ++ i)
    {
        for(int j = 0; j < arb[i].size(); ++ j)
            g<<arb[i][j]<<" ";
        g<<'\n';
    }*/

    sol(1);

    for(int i = 1; i <= n; ++ i)
        s += cost2[i];

    g<<s;


    return 0;
}