#include "job.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
ll u[MAXN], d[MAXN];
int n, FFFF;
deque <int> dp[MAXN];
deque <int> merge (deque <int> x, deque <int> y) {
ll aux[(int)x.size() + 1][(int)y.size() + 1] = {};
deque <ll> f((int)x.size() + 1, 0), g((int)y.size() + 1, 0);
for (int i = (int)x.size() - 1; i >= 0; i--) {
f[i] = f[i + 1] + u[x[i]];
}
for (int i = (int)y.size() - 1; i >= 0; i--) {
g[i] = g[i + 1] + u[y[i]];
}
for (int i = (int)x.size() - 1; i >= 0; i--) {
for (int j = (int)y.size() - 1; j >= 0; j--) {
aux[i][j] = min(aux[i + 1][j] + d[x[i]] * g[j], aux[i][j + 1] + d[y[j]] * f[i]);
}
}
deque <int> ret;
int a = 0, b = 0;
while (a < (int)x.size() && b < (int)y.size()) {
if (aux[a][b] == aux[a + 1][b] + d[x[a]] * g[b]) {
ret.push_back(x[a++]);
} else {
ret.push_back(y[b++]);
}
}
while (a < (int)x.size() || b < (int)y.size()) {
if (a < (int)x.size()) {
ret.push_back(x[a++]);
} else {
ret.push_back(y[b++]);
}
}
return ret;
}
void dfs (int pos) {
for (auto j : adj[pos]) {
dfs(j);
if (dp[j].empty()) {
swap(dp[pos], dp[j]);
} else dp[pos] = merge(dp[pos], dp[j]);
dp[j].clear();
}
dp[pos].push_front(pos);
}
ll scheduling_cost(vector<int> p, vector<int> _U, vector<int> _D) {
assert(!FFFF); FFFF = 1;
n = (int)p.size();
for (int i = 0; i < n; i++) {
u[i] = _U[i]; d[i] = _D[i];
if (p[i] != -1) {
adj[p[i]].push_back(i);
}
}
dfs(0);
auto ans = dp[0];
ll sum = 0, ret = 0;
for (auto i : ans) {
sum += u[i];
}
for (auto i : ans) {
ret += sum * (ll)d[i];
sum -= u[i];
}
return ret;
}
