#include "job.h"
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
#define ll long long
struct job{
int u, d, id;
bool operator < (const job &rhs) const{
return d * 1ll * rhs.u > u * 1ll * rhs.d;
}
};
int par[200005];
int find(int nw){
return par[nw] = (par[nw] == nw ? nw : find(par[nw]));
}
vector<int> adj[200005], ord;
void dfs(int nw){
ord.push_back(nw);
for(int nx : adj[nw]) dfs(nx);
}
long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d){
int n = p.size();
vector<int> U = u, D = d;
for(int i = 0; i < n; i ++)
par[i] = i;
priority_queue<job> pq;
for(int i = 1; i < n; i ++)
pq.push({u[i], d[i], i});
for(; pq.size();){
auto nw = pq.top();
pq.pop();
if(make_pair(nw.u, nw.d) != make_pair(U[nw.id], D[nw.id]))
continue;
int f = find(p[nw.id]);
par[nw.id] = f;
U[f] += U[nw.id];
D[f] += D[nw.id];
adj[f].push_back(nw.id);
if(f) pq.push({U[f], D[f], f});
}
dfs(0);
ll ans = 0ll, tim = 0ll;
for(int i : ord){
tim += d[i];
ans += tim * u[i];
}
return ans;
}
