#include "job.h"
#include <cstdlib>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 200000;
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int n;
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
long long cross(int x1, int y1, int x2, int y2) {
return (long long) x1 * y2 - (long long) x2 * y1;
}
int xx[N], yy[N];
int compare(int i, int j) {
long long c = cross(xx[i], yy[i], xx[j], yy[j]);
return c != 0 ? (c < 0 ? -1 : 1) : i - j;
}
int zz[N + 1], ll[N + 1], rr[N + 1], ii[N + 1], u_, l_, r_;
int node(int i) {
static int _ = 1;
zz[_] = rand_();
ll[_] = rr[_] = 0;
ii[_] = i;
return _++;
}
void split(int u, int i) {
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
int c = compare(ii[u], i);
if (c < 0) {
split(rr[u], i);
rr[u] = l_, l_ = u;
} else if (c > 0) {
split(ll[u], i);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
int first(int u) {
return ll[u] == 0 ? u : first(ll[u]);
}
int remove_first(int u) {
if (ll[u] == 0)
return rr[u];
ll[u] = remove_first(ll[u]);
return u;
}
int merge_(int u, int v) {
while (v) {
int w = first(v);
split(u, ii[w]);
u = merge(merge(l_, w), r_);
v = remove_first(v);
}
return u;
}
int sz[N], uu[N]; long long ans;
void dfs(int i) {
sz[i] = 1, uu[i] = 0;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
dfs(j);
uu[i] = sz[i] > sz[j] ? merge_(uu[i], uu[j]) : merge_(uu[j], uu[i]);
sz[i] += sz[j];
}
while (uu[i]) {
int w = first(uu[i]);
if (compare(i, ii[w]) < 0)
break;
ans += (long long) xx[i] * yy[ii[w]];
xx[i] += xx[ii[w]], yy[i] += yy[ii[w]];
uu[i] = remove_first(uu[i]);
}
uu[i] = merge(node(i), uu[i]);
}
long long scheduling_cost(vi pp, vi yy_, vi xx_) {
n = pp.size();
for (int i = 0; i < n; i++)
xx[i] = xx_[i], yy[i] = yy_[i];
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
for (int i = 1; i < n; i++)
append(pp[i], i);
ans = 0;
for (int i = 0; i < n; i++)
ans += (long long) xx[i] * yy[i];
dfs(0);
int x = 0;
while (uu[0]) {
int w = first(uu[0]);
ans += (long long) x * yy[ii[w]], x += xx[ii[w]];
uu[0] = remove_first(uu[0]);
}
for (int i = 0; i < n; i++)
free(ej[i]);
return ans;
}
