//#pragma GCC optimize("O3")
#include "job.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
int U[MAXN], D[MAXN];
bool operator<(pii lhs, pii rhs) {
return (ll)lhs.fi * (ll)rhs.se < (ll)rhs.fi * (ll)lhs.se;
}
struct cmp {
bool operator()(int lhs, int rhs) {
return mp(U[lhs],D[lhs]) < mp(U[rhs],D[rhs]);
}
};
priority_queue<int,vi,cmp> pq[MAXN];
int nx[MAXN], idx[MAXN];
vi ans;
void merge(int u) {
while (!pq[u].empty()) {
int v = pq[u].top();
if (mp(U[v], D[v]) < mp(U[u], D[u]))
return;
pq[u].pop();
nx[idx[u]] = v;
idx[u] = idx[v];
U[u] += U[v];
D[u] += D[v];
if (pq[u].size() < pq[v].size())
swap(pq[u], pq[v]);
while (!pq[v].empty()) {
pq[u].push(pq[v].top());
pq[v].pop();
}
}
}
void dfs(int u) {
ans.pb(u);
while (!pq[u].empty()) {
int v = pq[u].top(); pq[u].pop();
dfs(v);
}
}
ll scheduling_cost(vi p, vi u, vi d) {
int n = p.size();
for (int i = 0; i < n; i++) {
tie(idx[i],nx[i]) = mp(i,-1);
tie(U[i],D[i]) = mp(u[i], d[i]);
}
for (int i = n-1; i > 0; i--) {
merge(i);
pq[p[i]].push(i);
}
merge(0);
dfs(0);
sort(ans.begin(), ans.end(), [](int lhs, int rhs) {
return mp(U[lhs],D[lhs]) < mp(U[rhs],D[rhs]);
});
ll sm = 0, ret = 0;
for (int i = ans.size()-1; i >= 0; i--) {
for (int j = ans[i]; j != -1; j = nx[j]) {
sm += d[j];
ret += sm * u[j];
}
}
return ret;
}
