#include "job.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN = 2e5;
int n, nxt[mxN], ta[mxN];
vector<int> o;
ll u2[mxN], d2[mxN];
struct cmp {
bool operator()(const int &a, const int &b) {
return d2[a] * u2[b] > d2[b] * u2[a];
}
};
priority_queue<int, vector<int>, cmp> c[mxN];
void dfs(int u) {
o.push_back(u);
for (; c[u].size(); c[u].pop())
dfs(c[u].top());
}
ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
n = p.size();
memset(nxt, -1, 4 * n);
iota(ta, ta + n, 0);
for (int i = n - 1; ~i; --i) {
u2[i] = u[i];
d2[i] = d[i];
while (c[i].size()) {
int u = c[i].top();
if (cmp()(u, i))
break;
c[i].pop();
nxt[ta[i]] = u;
ta[i] = ta[u];
u2[i] += u2[u];
d2[i] += d2[u];
if (c[i].size() < c[u].size())
swap(c[i], c[u]);
for (; c[u].size(); c[u].pop())
c[i].push(c[u].top());
}
if (i)
c[p[i]].push(i);
}
dfs(0);
sort(o.begin(), o.end(), cmp());
ll t = 0, ans = 0;
for (int i = o.size() - 1; ~i; --i) {
for (int j = o[i]; ~j; j = nxt[j]) {
t += d[j];
ans += t * u[j];
}
}
return ans;
}
