#include "job.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long n,z=0,a[200069],wg[200069],dsu[200069],cc[200069];
vector<long long> al[200069];
struct cmp
{
bool operator()(pair<long long,long long> x,pair<long long,long long> y)
{
return x.fr*y.sc<y.fr*x.sc;
}
};
multiset<pair<long long,long long>,cmp> ms[200069];
multiset<pair<long long,long long>,cmp>::iterator it;
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
void jo(long long x,long long y)
{
x=fd(x);
y=fd(y);
if(cc[x]<cc[y])
{
swap(x,y);
}
for(it=ms[y].begin();it!=ms[y].end();it++)
{
ms[x].insert(*it);
}
dsu[y]=x;
cc[x]+=cc[y];
}
void dfs(long long x)
{
long long i,sz=al[x].size(),l;
dsu[x]=x;
cc[x]=1;
for(i=0;i<sz;i++)
{
l=al[x][i];
dfs(l);
jo(x,l);
}
for(it=ms[fd(x)].begin();it!=ms[fd(x)].end();)
{
if(a[x]*it->sc<=it->fr*wg[x])
{
break;
}
z-=it->fr*wg[x];
a[x]+=it->fr;
wg[x]+=it->sc;
it++;
ms[fd(x)].erase(prev(it));
}
ms[fd(x)].insert({a[x],wg[x]});
}
long long scheduling_cost(vector<int> pr,vector<int> wgg,vector<int> aa)
{
long long i,sm=0;
n=pr.size();
for(i=1;i<=n;i++)
{
a[i]=aa[i-1];
wg[i]=wgg[i-1];
if(i-1)
{
al[pr[i-1]+1].push_back(i);
}
}
dfs(1);
for(it=ms[fd(1)].begin();it!=ms[fd(1)].end();it++)
{
sm+=it->fr;
z+=it->sc*sm;
}
return z;
}
