#include "job.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define rmin(r, x) r = min(r, x)
#define rmax(r, x) r = max(r, x)
#define ends ' '
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 10;
struct Node {
int i;
ll u, d;
Node(int i, int u, int d) : i(i), u(u), d(d) {}
Node(void) : Node(0, 0, 0) {}
};
bool operator < (Node l, Node r) { return l.d * r.u > l.u * r.d; }
ll ans = 0;
int pa[maxn];
Node a[maxn];
priority_queue<Node> pq;
int fnd(int x) {
if(pa[x] < 0) return x;
return pa[x] = fnd(pa[x]);
}
void mrge(int i, int j) {
ans -= a[i].u * a[j].d;
a[i].u += a[j].u;
a[i].d += a[j].d;
}
void uni(int a, int b) {
a = fnd(a), b = fnd(b);
if(a == b) return;
pa[a] = b;
mrge(b, a);
}
long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
int n = p.size();
memset(pa, -1, sizeof(pa));
for(int i = 0; i < n; ++i) {
a[i] = Node(i, u[i], d[i]);
if(i) pq.emplace(a[i]);
}
while(!pq.empty()) {
Node t = pq.top(); pq.pop();
if(t.i == 0 || a[t.i].u != t.u) continue;
uni(t.i, p[t.i]);
pq.emplace(a[fnd(t.i)]);
}
ans += a[0].u * a[0].d;
return ans;
}
