#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
using namespace std;
typedef long long ll;
struct SuperNode {
int id;
ll total_duration;
ll total_urgency;
// We want the HIGHEST urgency/duration ratio.
// In a priority_queue, the "less" operator defines what goes to the BOTTOM.
// So: a < b means "a is less urgent than b".
bool operator<(const SuperNode& other) const {
// Equivalent to: (urgency / duration) < (other.urgency / other.duration)
return total_urgency * other.total_duration < other.total_urgency * total_duration;
}
};
// DSU Structure to keep track of merged nodes and the execution sequence
struct DSU {
vector<int> parent_map;
vector<int> sequence_tail;
vector<int> next_in_sequence;
DSU(int n) {
parent_map.resize(n);
iota(parent_map.begin(), parent_map.end(), 0); // parent_map[i] = i
sequence_tail.resize(n);
iota(sequence_tail.begin(), sequence_tail.end(), 0);
next_in_sequence.assign(n, -1);
}
int find(int i) {
if (parent_map[i] == i) return i;
return parent_map[i] = find(parent_map[i]);
}
// Connects the end of sequence 'u' to the start of sequence 'v'
void merge_sequences(int u, int v) {
int root_u = find(u);
int root_v = find(v);
// Link the physical sequence for the final walk
next_in_sequence[sequence_tail[root_u]] = root_v;
// Update the tail of the combined super-node
sequence_tail[root_u] = sequence_tail[root_v];
// DSU merge: v's root now points to u's root
parent_map[root_v] = root_u;
}
};
ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
int n = p.size();
DSU dsu(n);
vector<ll> curr_u(u.begin(), u.end());
vector<ll> curr_d(d.begin(), d.end());
priority_queue<SuperNode> pq;
// Initialize: Root (0) is special, others go in the PQ
for (int i = 1; i < n; i++) {
pq.push({i, curr_d[i], curr_u[i]});
}
// Tracking merged status to handle the "Lazy Deletion" in priority_queue
vector<bool> is_merged(n, false);
while (!pq.empty()) {
SuperNode top = pq.top();
pq.pop();
int v = dsu.find(top.id);
// Stale Check: If this node's stats don't match our current DSU stats, skip it
if (is_merged[top.id] || curr_u[v] != top.total_urgency || curr_d[v] != top.total_duration) {
continue;
}
// Find the parent of this super-node
// p[v] is the original parent, we find its current super-node root
int u_root = dsu.find(p[v]);
// Merge v into u_root
is_merged[v] = true;
dsu.merge_sequences(u_root, v);
// Update the parent's stats
curr_u[u_root] += top.total_urgency;
curr_d[u_root] += top.total_duration;
// If the new super-node isn't the root, put it back in the PQ
if (u_root != 0) {
pq.push({u_root, curr_d[u_root], curr_u[u_root]});
}
}
// Calculate final cost by traversing the linked sequence starting at root (0)
ll total_cost = 0;
ll current_time = 0;
int curr = 0;
while (curr != -1) {
current_time += d[curr];
total_cost += current_time * u[curr];
curr = dsu.next_in_sequence[curr];
}
return total_cost;
}
