#include "job.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<ll> link, sz;
vector<ll> u, d;
vector<vector<int>> seq;
DSU(int n, vector<int> &U, vector<int> &D) {
sz.resize(n, 1);
link.resize(n);
iota(link.begin(), link.end(), 0);
seq.resize(n);
for (int i = 0; i < n; i++) seq[i].push_back(i);
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) {
while (x != link[x]) x = link[x];
return x;
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
sz[a] += b;
link[b] = a;
seq[a].push_back(b);
u[a] += u[b];
d[a] += d[b];
}
ll cur_time = 0, ans = 0;
void calc(int a, vector<int> &U, vector<int> &D) {
for (int i = 0; i < seq[a].size(); i++) {
if (seq[a][i] == a) {
cur_time += 1ll*D[seq[a][i]];
ans += 1ll*cur_time*U[seq[a][i]];
}
else calc(seq[a][i], U, D);
}
}
};
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});
}
dsu.calc(0, u, d);
return dsu.ans;
}
