#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "jobscheduling"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Cho 1 cây n đỉnh:
Cv i có parent là pi.
Cv i hoàn thành ở thời gian i có cost là t * u[i].
Cv i có thời gian hoàn thành là di.
Sắp xếp các cv sao cho các công việc pi luôn đứng trước i (trừ thằng 1).
subtask 1: cây đường thẳng.
Thì ta làm tuần tự.
subtask 2: Không có quan hệ ràng buộc cha con và d[i] = 1.
sort theo độ quan trọng của nó.
subtask 3: Không có quan hệ ràng buộc cha và con.
sort các đỉnh theo di / ui tăng dần.
Ta chứng minh được rằng nếu nó độc lập thì cách trên là tối ưu.
subtask 4: cây đường thẳng nhưng đỉnh 0 không nằm ở đầu đoạn thẳng.
Khi ta lấy 0 thì nó sẽ tách thành 2 đoạn thẳng.
**/
const int MAXN = 3e5 + 9;
int n;
namespace subtask1{
bool check(){
return n <= 10;
}
int solve(vector<int> p, vector<int> u, vector<int> d){
int permutation[12], position[12];
iota(permutation + 0, permutation + n, 0);
int res = inf;
do{
int cur = 0;
int ti =0;
FOR(i, 0, n - 1){
position[permutation[i]] = i;
cur += (ti += d[permutation[i]]) * u[permutation[i]];
}
bool kt = true;
FOR(i, 1, n - 1){
if (position[p[i]] > position[i]) kt = false;
}
if (kt) minimize(res, cur);
} while(next_permutation(permutation, permutation + n));
return res;
}
}
namespace subtask6{
bool check(){
return true;
}
struct pii{
ll d, u, id;
pii(int _d = 0, int _u = 0, int _id = 0): d(_d), u(_u), id(_id){}
friend inline pii operator + (const pii &a, const pii &b){
return pii(a.d + b.d, a.u + b.u, a.id);
}
friend inline pii operator - (const pii &a, const pii &b){
return pii(a.d - b.d, a.u - b.u, a.id);
}
friend inline bool operator < (const pii &a, const pii &b){
return a.d * b.u < a.u * b.d;
}
friend inline bool operator > (const pii &a, const pii &b){
return (!(a < b));
}
};
priority_queue<pii, vector<pii>, greater<pii>> pq[MAXN];
vector<int> g[MAXN];
pii a[MAXN];
void dfs(int u){
for(int v: g[u]){
dfs(v); pq[u].push(a[v]);
}
while(!pq[u].empty()){
if (pq[u].top() < a[u]){
a[u] = a[u] + pq[u].top();
int id = pq[u].top().id;
pq[u].pop();
// printf("MERGE: %lld %lld %lld\n", a[id].d, a[id].u, u, a[u].d, a[u].u);
if (pq[u].size() < pq[id].size()) swap(pq[u], pq[id]);
while(!pq[id].empty()){
pq[u].push(pq[id].top());
pq[id].pop();
}
}
else break;
}
}
long long get(vector<int> p, vector<int> u, vector<int> d){
FOR(i, 1, n - 1){
g[p[i]].pb(i);
}
FOR(i, 0, n - 1){
a[i] = pii(d[i], u[i], i);
}
dfs(0);
ll res = 0, cur = 0;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push(a[0]);
while(!q.empty()){
int id = q.top().id;
q.pop();
res += (cur += d[id]) * u[id];
// printf("%lld\n", id);
for(int v: g[id]){
q.push(a[v]);
}
}
return res;
}
}
//d[i] / u[i];
long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d){
n = u.size();
// if (subtask1::check()) return subtask1::solve(p, u, d);
if (subtask6::check()) return subtask6::get(p, u, d);
return 0;
}
