#include "tree.h"
#include <cstdlib>
#include <cstring>
using namespace std;
typedef vector<int> vi;
const int N = 200000, M = N * 4;
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int pp[N], ww[N];
int *ej[N], eo[N], ii[N], 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;
}
int *vv;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (vv[ii[j]] == vv[i_])
j++;
else if (vv[ii[j]] < vv[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int tt[M]; long long aa[M], bb[M];
int tt_[M]; long long aa_[M], bb_[M];
int hh[M], m;
char active[N]; int ds[N], ss[N], l, r;
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
void join(int i, int j, int w) {
i = find(i);
j = find(j);
if (i == j)
return;
tt[m] = ss[i], aa[m] = (long long) -(ss[i] + 1) * w, bb[m] = w, m++;
tt[m] = ss[j], aa[m] = (long long) -(ss[j] + 1) * w, bb[m] = w, m++;
tt[m] = ss[i] + ss[j], aa[m] = (long long) (ss[i] + ss[j] + 1) * w, bb[m] = -w, m++;
if (ds[i] > ds[j])
ds[i] = j, ss[j] += ss[i];
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, ss[i] += ss[j];
}
}
long long c;
void init(vi pp_, vi ww_) {
n = pp_.size();
for (int i = 0; i < n; i++)
pp[i] = pp_[i], ww[i] = ww_[i];
for (int i = 0; i < n; i++)
ii[i] = i;
vv = ww, sort(ii, 0, n);
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (int j = 1; j < n; j++)
append(pp[j], j);
c = 0;
for (int i = 0; i < n; i++)
if (eo[i] == 0)
c += ww[i];
memset(active, 0, n * sizeof *active), memset(ds, -1, n * sizeof *ds);
for (int i = 0; i < n; i++)
ss[i] = max(eo[i] - 1, 0);
for (int h = n - 1; h >= 0; h--) {
int i = ii[h], w = ww[i];
active[i] = 1;
tt[m] = ss[i], aa[m] = (long long) (ss[i] + 1) * w, bb[m] = -w, m++;
if (i > 0 && active[pp[i]] == 1)
join(i, pp[i], w);
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (active[j] == 1)
join(i, j, w);
}
}
for (int h = 0; h < m; h++)
hh[h] = h;
vv = tt, sort(hh, 0, m);
for (int h = m - 1; h >= 0; h--) {
int h_ = hh[h];
tt_[h] = tt[h_], aa_[h] = aa_[h + 1] + aa[h_], bb_[h] = bb_[h + 1] + bb[h_];
}
}
long long query(int l, int r) {
int lower = -1, upper = m;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (tt_[h] >= r / l)
upper = h;
else
lower = h;
}
return aa_[upper] * l + bb_[upper] * r + c * l;
}
