#include "job.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct job{
ll s, d;
job(ll s, ll d) : s(s), d(d) {}
job() {}
bool operator < (job t) const {
return s * t.d < d * t.s; }
};
priority_queue <job> S[202020];
vector <int> T[202020];
ll ans;
void merge(int u, int v)
{
auto &P = S[u], &Q = S[v];
if(P.size() < Q.size()) swap(P, Q);
for(; !Q.empty(); Q.pop()) P.push(Q.top());
}
void insert(int i, job x)
{
auto &P = S[i];
for(; !P.empty(); P.pop()){
job t = P.top();
if(t < x) break;
ans += t.s * x.d;
x.s += t.s; x.d += t.d;
}
P.push(x);
}
ll scheduling_cost(vector <int> P, vector <int> U, vector<int> D)
{
int n, i;
n = P.size();
for(i = 0; i < n; i ++){
if(i) T[P[i]].push_back(i);
ans += U[i] * D[i];
}
for(i = n - 1; i >= 0; i --){
for(int &t: T[i]){
merge(i, t);
}
insert(i, job(U[i], D[i]));
}
insert(0, job(-2e9, 0));
return ans;
}
