#include "job.h"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
struct Job {
int64 u, d, id;
Job(int _u, int _d, int _id) : u(_u), d(_d), id(_id) {}
bool operator < (const Job &rhs) const {
return d * rhs.u < rhs.d * u;
}
};
int64 scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
int N = p.size();
vector<vector<int>> ch(N);
for (int i = 1; i < N; ++i) ch[p[i]].emplace_back(i);
multiset<Job> jobs;
for (int i = 0; i < N; ++i) jobs.emplace(u[i], d[i], i);
int64 tim = 0, ans = 0;
while (jobs.size()) {
Job job = *begin(jobs);
jobs.erase(begin(jobs));
// cerr << "(" << job.u << ", " << job.d << ", " << job.id << ")\n";
if (u[job.id] != job.u or d[job.id] != job.d) continue;
// cerr << "(" << job.u << ", " << job.d << ", " << job.id << ")\n";
if (p[job.id] == -1) {
ans += job.u * (tim += job.d);
for (int x : ch[job.id]) p[x] = -1;
ch[job.id].clear();
}
else {
ans -= u[p[job.id]] * job.d;
int64 new_u = u[p[job.id]] + job.u;
int64 new_d = d[p[job.id]] + job.d;
// if (ch[p[job.id]].size() <= ch[job.id].size()) {
// u[job.id] = new_u, d[job.id] = new_d;
// for (int x : ch[p[job.id]]) {if (x != job.id) ch[job.id].emplace_back(x), p[x] = job.id;}
// ch[p[job.id]].clear();
// if (p[p[job.id]] != -1) ch[p[p[job.id]]].emplace_back(job.id);
// p[job.id] = p[p[job.id]];
// jobs.emplace(u[job.id], d[job.id], job.id);
// }
// else {
u[p[job.id]] = new_u, d[p[job.id]] = new_d;
for (int x : ch[job.id]) ch[p[job.id]].emplace_back(x), p[x] = p[job.id];
ch[job.id].clear();
jobs.emplace(u[p[job.id]], d[p[job.id]], p[job.id]);
// }
}
}
return ans;
}
