#include "job.h"
#include <vector>
#include <set>
#include <cstdio>
const int MAX_N = 200000;
long long res;
std::vector<int> graph[MAX_N];
struct DSUNode {
int nod, sd, su;
DSUNode(int _nod, int _sd, int _su) {
nod = _nod;
sd = _sd;
su = _su;
}
bool operator< (const DSUNode x) const {
return (long long)sd * x.su < (long long)su * x.sd ||
((long long)sd * x.su == (long long)su * x.sd && nod < x.nod);
}
};
struct DSU {
int sd, su;
std::set<DSUNode> extended_neighbours;
} dsu[MAX_N];
void join(int a, int b) {
res = res + (long long)dsu[a].sd * dsu[b].su;
dsu[a].sd += dsu[b].sd;
dsu[a].su += dsu[b].su;
dsu[a].extended_neighbours.erase({b, dsu[b].sd, dsu[b].su});
if(dsu[a].extended_neighbours.size() < dsu[b].extended_neighbours.size())
dsu[a].extended_neighbours.swap(dsu[b].extended_neighbours);
for(auto it: dsu[b].extended_neighbours)
dsu[a].extended_neighbours.insert(it);
dsu[b].extended_neighbours.clear();
}
void dfs(int nod) {
for(auto it: graph[nod]) {
dfs(it);
dsu[nod].extended_neighbours.insert({it, dsu[it].sd, dsu[it].su});
}
while(!dsu[nod].extended_neighbours.empty()
&& *dsu[nod].extended_neighbours.begin() < DSUNode(nod, dsu[nod].sd, dsu[nod].su))
join(nod, dsu[nod].extended_neighbours.begin()->nod);
}
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
int n = u.size();
for(int i = 0; i < n; ++i) {
dsu[i] = {d[i], u[i]};
res = res + (long long)u[i] * d[i];
}
for(int i = 1; i < n; ++i)
graph[p[i]].push_back(i);
dfs(0);
while(!dsu[0].extended_neighbours.empty())
join(0, dsu[0].extended_neighbours.begin()->nod);
return res;
}
