#include "job.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
bool comp(const array<ll,2>& a, const array<ll,2>& b) {
if(a[1]*b[0]==b[1]*a[0]) {
return a[1]<b[1];
}
return a[1]*b[0] < b[1]*a[0];
}
// abcde
struct DS {
vector<array<ll,2>> ts;
void root(int u,int d) { // O(1)
ts.push_back({ts.empty()?u:ts.back()[0]+u,d});
}
void merge(DS& o) {
vector<array<ll,2>> together;
auto it = ts.rbegin(), it2 = o.ts.rbegin();
ll u = ts.back()[0];
ll ou = o.ts.back()[0];
while(it!=ts.rend() or it2!=o.ts.rend()) {
if(it2==o.ts.rend() or (it!=ts.rend() and comp(*it,*it2))) {
(*it)[0]+=ou;
together.push_back(*it);
++it;
if(it==ts.rend()) u=0;
else u = (*it)[0];
} else {
(*it2)[0]+=u;
together.push_back(*it2);
++it2;
if(it2==o.ts.rend()) ou=0;
else ou = (*it2)[0];
}
}
swap(ts,together);
reverse(all(ts));
}
ll ans() {
ll res=0;
ll pd=0;
for(auto& [u,d] : ts) {
res+=u*d;
}
return res;
}
};
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
// merge chains?
int n = p.size();
// just loop backwards, and maintain those?
vector<DS> dp(n);
for(int i=n-1;i>=0;--i) {
// add root
dp[i].root(u[i],d[i]);
if(p[i]!=-1) {
if(dp[p[i]].ts.empty()) swap(dp[i],dp[p[i]]);
else dp[p[i]].merge(dp[i]);
}
}
return dp[0].ans() ;
}
