// trans rights
#include <bits/extc++.h>
using namespace std;
#include "job.h"
using ll = long long;
using base = complex<double>;
#define up(k, N) for (int k = 1; k <= N; k++)
#define down(k, N) for (int k = N; k >= 1; k--)
#define f0(A) memset(A, 0, sizeof(A))
#define f3(A) memset(A, 0x3f, sizeof(A))
#define all(A) begin(A), end(A)
struct Job
{
int id;
ll d, u;
bool operator < (const Job &a) const
{
return d * a.u > a.d * u;
}
bool operator != (const Job &a) const
{
return d != a.d or u != a.u;
}
};
Job jobs[200069];
bool taken[200069];
int parents[200069];
int getp(int i)
{
return i == parents[i] ? i : parents[i] = getp(parents[i]);
}
ll scheduling_cost(vector<int> P, vector<int> U, vector<int> D)
{
int N = (int) P.size();
priority_queue<Job> pq;
ll ans = 0;
for (int i = 0; i < N; i++)
{
Job job;
job.id = i;
job.u = U[i];
job.d = D[i];
ans += job.u * job.d;
jobs[i] = job;
pq.push(job);
parents[i] = i;
}
while (not pq.empty())
{
auto job = pq.top();
pq.pop();
if (job != jobs[job.id] or taken[job.id])
continue;
int p = P[job.id];
if (p == -1)
{
}else{
auto &pj = jobs[getp(p)];
ans += pj.d * job.u;
pj.d += job.d;
pj.u += job.u;
pq.push(pj);
parents[job.id] = getp(p);
}
taken[job.id] = true;
}
return ans;
}
