#include "job.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
ll u[MAXN], d[MAXN];
int n;
struct DSU {
int par[MAXN];
void init () {
for (int i = 0; i < n; i++) {
par[i] = i;
}
}
int find (int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
void merge (int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (x < y) swap(x, y);
par[x] = y;
}
} cur;
/*
p[x], y, x
if x is node with maximum u[x] / d[x], it should be placed right after p[x]
otherwise, u[x] / d[x] > u[y] / d[y], so u[x] * d[y] > u[y] * d[x], so optimal to move x
to the right
keep taking such a node and merge it with its parent
*/
struct cmp {
bool operator()(const int &x, const int &y) const {
if (u[x] * d[y] == u[y] * d[x]) {
return x < y;
}
return u[x] * d[y] > u[y] * d[x];
}
};
deque <int> ord[MAXN];
ll scheduling_cost(vector<int> p, vector<int> _U, vector<int> _D) {
n = (int)p.size();
for (int i = 0; i < n; i++) {
u[i] = _U[i]; d[i] = _D[i];
ord[i].push_back(i);
}
cur.init();
set <int, cmp> pq;
for (int i = 1; i < n; i++) {
pq.insert(i);
}
while (!pq.empty()) {
int k = *(pq.begin());
assert(k != 0);
pq.erase(k);
p[k] = cur.find(p[k]);
if (ord[p[k]].size() > ord[k].size()) {
for (auto i : ord[k]) {
ord[p[k]].push_back(i);
}
ord[k].clear();
} else {
swap(ord[p[k]], ord[k]);
reverse(ord[k].begin(), ord[k].end());
for (auto i : ord[k]) {
ord[p[k]].push_front(i);
}
}
pq.erase(p[k]);
u[p[k]] += u[k]; d[p[k]] += d[k];
if (p[k] != 0) pq.insert(p[k]);
cur.merge(k, p[k]);
}
ll sum = 0, ans = 0;
for (auto i : ord[0]) {
sum += (ll)_D[i]; ans += (ll)_U[i] * sum;
}
return ans;
}
