#include "job.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> ord, t;
vector<vector<int>> v;
struct frac
{
int x, y, id;
};
struct cmp
{
bool operator () (frac a, frac b)
{
return (ll) a.x * b.y > (ll) b.x * a.y;
}
};
void dfs(int node)
{
ord.push_back(node);
for(auto it : v[node])
dfs(it);
}
int boss(int x)
{
if(x == t[x]) return x;
return t[x] = boss(t[x]);
}
ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d)
{
priority_queue<frac, vector<frac>, cmp> heap;
vector<int> U, D;
U = u;
D = d;
int i, n = p.size();
for(i=1; i<n; ++i)
heap.push({D[i], U[i], i});
t.resize(n);
for(i=0; i<n; ++i)
t[i] = i;
v.resize(n);
while(heap.size())
{
auto el = heap.top();
heap.pop();
if(make_pair(D[el.id], U[el.id]) != make_pair(el.x, el.y)) continue;
int father = boss(p[el.id]);
t[el.id] = father;
D[father] += D[el.id];
U[father] += U[el.id];
v[father].push_back(el.id);
if(father)
heap.push({D[father], U[father], father});
}
dfs(0);
ll sum = 0, ans = 0;
for(auto it : ord)
{
sum += d[it];
ans += sum * u[it];
}
return ans;
}
