#include "job.h"
#include <vector>
#include<set>
#include<iostream>
#define LL long long
#define MAXN 300005
using namespace std;
struct Job {LL wt, t;};
class CompareClass {
public:
bool operator() (Job a, Job b) {
return(a.wt*b.t > a.t*b.wt); //wt, time
}
};
int N, big[MAXN];
LL U[MAXN], D[MAXN], ans; //cost, time
vector<int> chd[MAXN];
multiset<Job, CompareClass> Order[MAXN];
int dfs(int u) {
big[u]=u;
for (auto v: chd[u]) {
int p = dfs(v);
while (Order[p].size()) {
Job f = *Order[p].begin();
if (f.wt*D[u] >= f.t*U[u]) {
ans-=f.t*U[u];
U[u]+=f.wt, D[u]+=f.t;
Order[p].erase(Order[p].begin());
} else {
break;
}
}
}
Order[big[u]].insert(Job {U[u], D[u]});
for (auto v: chd[u]) {
if (Order[big[v]].size() > Order[big[u]].size()) {
swap(big[u], big[v]);
}
for (Job j: Order[big[v]]) {
Order[big[u]].insert(j);
}
}
return(big[u]);
}
LL scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
N=p.size();
for(int i=0; i<N; i++) {
if (i) {chd[p[i]].push_back(i);}
U[i]=u[i], D[i]=d[i];
}
LL time=0;
int ptr = dfs(0);
for (Job j: Order[ptr]) {
time+=j.t;
ans+=j.wt*time;
}
return(ans);
}
