#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) {
deque <int> ret;
while (!x.empty() && !y.empty()) {
if (u[x.back()] < u[y.back()]) {
ret.push_back(x.back()); x.pop_back();
} else {
ret.push_back(y.back()); y.pop_back();
}
}
while (!x.empty()) {
ret.push_back(x.back()); x.pop_back();
}
while (!y.empty()) {
ret.push_back(y.back()); y.pop_back();
}
reverse(ret.begin(), ret.end());
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;
}
