#include "job.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=2e5+5;
struct info
{
ll c0, c1, idx, ver;
bool operator< (const info &o) const {return c1*o.c0<c0*o.c1;}
} lst[nx];
ll n, dsu[nx], res, t;
multiset<info> s;
int find(int x)
{
if (dsu[x]==x) return x;
return dsu[x]=find(dsu[x]);
}
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
n=p.size();
for (int i=0; i<n; i++)
{
lst[i].c0=u[i];
lst[i].c1=d[i];
lst[i].idx=i;
lst[i].ver=0;
res+=u[i]*d[i];
if (i) s.insert(lst[i]);
}
while (!s.empty())
{
auto cur=*s.begin();
s.erase(s.begin());
if (lst[cur.idx].ver!=cur.ver) continue;
int pv=find(p[cur.idx]);
dsu[cur.idx]=pv;
res+=lst[pv].c1*cur.c0;
lst[pv].c0+=cur.c0;
lst[pv].c1+=cur.c1;
lst[pv].ver=++t;
if (pv) s.insert(lst[pv]);
}
return res;
}
