#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const int N = 2e5+5;
struct node{
ll lca,d,u,id;
deque<int> dq;
bool operator < (const node &oth) const{
if(d*oth.u != oth.d*u) return d*oth.u < oth.d*u;
return lca < oth.lca;
}
}lab[N];
int h[N];
int findpar(int u){
if(lab[u].id < 0) return u;
return lab[u].id = findpar(lab[u].id);
}
bool unite(int u,int v){
u=findpar(u);
v=findpar(v);
if(u == v) return false;
//u cha v con
if(lab[u].id <= lab[v].id){
//cerr<<u<<"has\n";
while(!lab[v].dq.empty()){
lab[u].dq.push_back(lab[v].dq.front());
lab[v].dq.pop_front();
}
}else{
//cerr<<v<<"has\n";
while(!lab[u].dq.empty()){
lab[v].dq.push_front(lab[u].dq.back());
lab[u].dq.pop_back();
}
}
if(lab[u].id > lab[v].id) swap(u,v);
lab[u].d += lab[v].d;
lab[u].u += lab[v].u;
lab[u].lca = (h[lab[u].lca] < h[lab[v].lca] ? lab[u].lca : lab[v].lca);
lab[u].id += lab[v].id;
lab[v].id = u;
//cerr<<u<<' '<<lab[2].dq.size()<<'\n';
return true;
}
ll scheduling_cost(vector<int> p,vector<int> u,vector<int> d){
int n=p.size();
set<node> s;
for(int i=1;i<n;i++){
h[i]=h[p[i]]+1;
}
for(int i=0;i<n;i++){
lab[i].lca=i;
lab[i].d=d[i];
lab[i].u=u[i];
lab[i].id=-1;
lab[i].dq.push_back(i);
if(i != 0) s.insert(lab[i]);
}
//cerr<<lab[0].dq.size()<<' '<<lab[1].d<<'\n';
while(!s.empty()){
node e=*s.begin();
s.erase(s.begin());
int par=p[e.lca];
int pp=findpar(par);
if(lab[pp].lca != 0){
s.erase(lab[pp]);
}
unite(pp,e.lca);
pp=findpar(pp);
//cerr<<pp<<' '<<lab[pp].dq.size()<<'\n';
if(lab[pp].lca != 0){
s.insert(lab[pp]);
}
}
ll ans=0;
int p1=findpar(0);
deque<int> dq=lab[p1].dq;
//cerr<<p1<<'\n';
ll sumd=0;
while(!dq.empty()){
sumd += d[dq.front()];
ans += sumd*u[dq.front()];
dq.pop_front();
}
return ans;
}
//signed main(){
// ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
// if(fopen("text.inp","r")){
// freopen("text.inp","r",stdin);
// }
// cout<<scheduling_cost({-1,0,0},{5,2,5},{3,4,1});
//}
