#include "job.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 13;
int dsu[N];
int ufds(int u){
return dsu[u] = u == dsu[u] ? u : ufds(dsu[u]);
}
struct Comp{
const bool operator() (tuple<int,int,int> a,tuple<int,int,int> b){
return get<0>(a) * 1LL * get<1>(b) < get<1>(a) * 1LL * get<0>(b);
}
};
long long scheduling_cost(vector<int> p,vector<int> u,vector<int> d){
int n = p.size();
iota(dsu,dsu+n,0);
long long cost = 0;
for(int i=0;i<n;i++) cost += u[i] * 1LL * d[i];
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int> >,Comp> pq;
for(int i=0;i<n;i++) pq.emplace(u[i],d[i],i);
while(!pq.empty()){
auto curr = pq.top();
int ux = get<0>(curr);
int id = get<2>(curr);
pq.pop();
if(ux != u[id]) continue;
if(id){
int pr = ufds(p[id]);
cost += u[id] * 1LL * d[pr];
dsu[id] = pr;
u[pr] += u[id];
d[pr] += d[id];
pq.emplace(u[pr],d[pr],pr);
}
}
return cost;
}
