#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;
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 nxt[N],head[N],tail[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
nxt[tail[u]]=head[v];
int ta=tail[v];
int he=head[u];
if(lab[u].id > lab[v].id) swap(u,v);
head[u]=he;
tail[u]=ta;
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;
head[i]=tail[i]=i;
nxt[i]=-1;
lab[i].d=d[i];
lab[i].u=u[i];
lab[i].id=-1;
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);
int curr=0;
//cerr<<p1<<'\n';
ll sumd=0;
while(curr != -1){
sumd += d[curr];
ans += sumd*u[curr];
curr=nxt[curr];
}
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});
//}
