#include "job.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
const int N = 2e5+5432, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321, mod = 998244353;
struct Element
{
ll u,t;
bool operator < (const Element &element) const
{
return t*element.u < element.t*u;
}
};
ll n;
ll P[N], U[N], T[N];
vector<Element> A[N];
vector<ll> G[N];
void DFS(ll v)
{
for(auto x : G[v])
{
DFS(x);
int wsk = -1, dod = -1;
vector<Element> P;
for(auto y : A[x])
{
Element akt = {0,0};
int wsk2 = wsk;
for(int i = wsk2+1; i < (int)A[v].size(); ++i)
{
akt = {akt.u+A[v][i].u,akt.t+A[v][i].t};
if(akt < y)
{
wsk = i;
akt = {0,0};
}
}
while(dod < wsk) ++dod, P.pb(A[v][dod]);
P.pb(y);
}
while(dod+1 < (int)A[v].size()) ++dod, P.pb(A[v][dod]);
A[v] = P;
}
vector<Element> akt = {{U[v],T[v]}};
for(auto x : A[v]) akt.pb(x);
A[v] = akt;
}
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
n = (ll)p.size();
rep(i,n) P[i] = p[i], U[i] = u[i], T[i] = d[i];
for(int i = 1; i < n; ++i)
{
G[P[i]].pb(i);
}
DFS(0);
ll t = 0, ans = 0;
for(auto x : A[0])
{
t += x.t;
ans += t*x.u;
}
return ans;
}
