#include "job.h"
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define sz(x) int(x.size())
ll res = 0;
const int mx = 200'000;
struct dsu
{
vi par = vi(1+mx);
vi st = vi(1+mx, 1);
vi peak = vi(1+mx);
dsu()
{
for(int i = 0; i <= mx; i++)
{
par[i] = i;
peak[i] = i;
}
}
int root(int u)
{
if(par[u] == u) return u;
else return (par[u] = root(par[u]));
}
int getpeak(int u)
{
return peak[root(u)];
}
bool join(int u, int v, int p)
{
u = root(u);
v = root(v);
if(u == v)
return 0;
if(st[u] < st[v])
swap(u, v);
par[v] = u;
st[u] += st[v];
peak[u] = p;
return 1;
}
};
int n;
vi p;
vll u, d;
struct temple
{
int i;
};
bool operator < (temple A, temple B)
{
if(d[A.i]*u[B.i] == d[B.i]*u[A.i])
return A.i < B.i;
else
return d[A.i]*u[B.i] < d[B.i]*u[A.i];
}
ll scheduling_cost(vi p_, vi u_, vi d_)
{
p = p_;
n = sz(p);
u = d = vll(n);
for(int i = 0; i < n; i++)
{
u[i] = u_[i];
d[i] = d_[i];
}
dsu ds;
for(int i = 0; i < n; i++)
res += u[i]*d[i];
set<temple> S;
for(int i = 1; i < n; i++)
S.insert(temple{i});
//combined values are stored at the paek
for(int t = 0; t < n-1; t++)
{
int a = S.begin()->i;
S.erase(S.begin());
int pa = ds.getpeak(a);
int b = p[pa];
int pb = ds.getpeak(b);
res += d[pb] * u[pa];
ds.join(pa, pb, pb);
if(pb == 0)
{
d[pb] += d[pa];
u[pb] += u[pa];
}
else
{
S.erase(temple{pb});
d[pb] += d[pa];
u[pb] += u[pa];
S.insert(temple{pb});
}
}
return res;
}
