#include "job.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> link, sz;
vector<ll> u, d;
vector<int> nxt, tail;
DSU(int n, vector<int> &U, vector<int> &D) {
sz.resize(n, 1);
link.resize(n);
iota(link.begin(), link.end(), 0);
tail = link;
nxt.resize(n, -1);
u.resize(n);
d.resize(n);
for (int i = 0; i < n; i++) {
u[i] = U[i];
d[i] = D[i];
}
}
int find(int x) {
queue<int> q;
while (x != link[x]) {
q.push(x);
x = link[x];
}
while (!q.empty()) {
link[q.front()] = link[x];
q.pop();
}
return x;
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
sz[a] += b;
link[b] = a;
nxt[tail[a]] = b;
tail[a] = tail[b];
u[a] += u[b];
d[a] += d[b];
}
};
struct s {
ll u, d;
int i;
bool operator<(const s &other) const {
// u/d < other.u/other.d
return 1ll*u*other.d < 1ll*d*other.u;
}
};
long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
int n = p.size();
vector<vector<int>> adj(n);
for (int i = 1; i < n; i++) adj[p[i]].push_back(i);
priority_queue<s> pq;
for (int i = 1; i < n; i++) pq.push({u[i], d[i], i});
DSU dsu(n, u, d);
while (!pq.empty()) {
s a = pq.top();
pq.pop();
int x = dsu.find(a.i);
if (x != a.i || dsu.u[x] != a.u || dsu.d[x] != a.d) continue;
int y = dsu.find(p[a.i]);
dsu.merge(y, x);
if (y != 0) pq.push({dsu.u[y], dsu.d[y], y});
}
ll cur_time = 0, ans = 0;
int cur = 0;
while (cur != -1) {
cur_time += d[cur];
ans += cur_time*u[cur];
cur = dsu.nxt[cur];
}
return ans;
}
