#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
struct Node {
int lc, rc;
long long mass, p_mass;
} tr[10000000];
int node_cnt = 0;
inline int new_node() {
int u = ++node_cnt;
tr[u].lc = tr[u].rc = 0;
tr[u].mass = tr[u].p_mass = 0;
return u;
}
inline void pushup(int u) {
tr[u].mass = tr[tr[u].lc].mass + tr[tr[u].rc].mass;
tr[u].p_mass = tr[tr[u].lc].p_mass + tr[tr[u].rc].p_mass;
}
long long P_val[MAXN * 2 + 5];
void add_mass(int &u, int l, int r, int idx, long long m) {
if (!u) u = new_node();
if (l == r) {
tr[u].mass += m;
tr[u].p_mass += m * P_val[idx];
return;
}
int mid = (l + r) >> 1;
if (idx <= mid) add_mass(tr[u].lc, l, mid, idx, m);
else add_mass(tr[u].rc, mid + 1, r, idx, m);
pushup(u);
}
int merge(int u, int v, int l, int r) {
if (!u || !v) return u ? u : v;
if (l == r) {
tr[u].mass += tr[v].mass;
tr[u].p_mass += tr[v].p_mass;
return u;
}
int mid = (l + r) >> 1;
tr[u].lc = merge(tr[u].lc, tr[v].lc, l, mid);
tr[u].rc = merge(tr[u].rc, tr[v].rc, mid + 1, r);
pushup(u);
return u;
}
long long query_mass(int u, int l, int r, int ql, int qr) {
if (!u || ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return tr[u].mass;
int mid = (l + r) >> 1;
return query_mass(tr[u].lc, l, mid, ql, qr) + query_mass(tr[u].rc, mid + 1, r, ql, qr);
}
long long query_p_mass(int u, int l, int r, int ql, int qr) {
if (!u || ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return tr[u].p_mass;
int mid = (l + r) >> 1;
return query_p_mass(tr[u].lc, l, mid, ql, qr) + query_p_mass(tr[u].rc, mid + 1, r, ql, qr);
}
void clear_range(int &u, int l, int r, int ql, int qr) {
if (!u || ql > r || qr < l) return;
if (ql <= l && r <= qr) {
u = 0;
return;
}
int mid = (l + r) >> 1;
clear_range(tr[u].lc, l, mid, ql, qr);
clear_range(tr[u].rc, mid + 1, r, ql, qr);
pushup(u);
}
void keep_prefix(int &u, int l, int r, long long &target) {
if (!u) return;
if (target >= tr[u].mass) {
target -= tr[u].mass;
return;
}
if (target == 0) {
u = 0;
return;
}
if (l == r) {
tr[u].mass = target;
tr[u].p_mass = target * P_val[l];
target = 0;
return;
}
int mid = (l + r) >> 1;
keep_prefix(tr[u].lc, l, mid, target);
keep_prefix(tr[u].rc, mid + 1, r, target);
pushup(u);
}
int N, M;
vector<int> children[MAXN];
long long W[MAXN];
int idx_minus_W[MAXN];
int idx_plus_W[MAXN];
int idx_0;
long long f[MAXN];
int root[MAXN];
void init(vector<int> P, vector<int> W_in) {
N = W_in.size();
for (int i = 0; i < N; i++) W[i] = W_in[i];
for (int i = 1; i < N; i++) children[P[i]].push_back(i);
vector<long long> vals;
vals.push_back(0);
for (int i = 0; i < N; i++) {
vals.push_back(W[i]);
vals.push_back(-W[i]);
}
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
M = vals.size();
for (int i = 0; i < M; i++) {
P_val[i + 1] = vals[i];
}
idx_0 = lower_bound(P_val + 1, P_val + M + 1, 0LL) - P_val;
for (int i = 0; i < N; i++) {
idx_minus_W[i] = lower_bound(P_val + 1, P_val + M + 1, -W[i]) - P_val;
idx_plus_W[i] = lower_bound(P_val + 1, P_val + M + 1, W[i]) - P_val;
}
}
long long query(int L, int R) {
node_cnt = 0;
long long Delta = R - L;
for (int u = N - 1; u >= 0; u--) {
if (children[u].empty()) {
root[u] = 0;
if (Delta > 0) add_mass(root[u], 1, M, idx_plus_W[u], Delta);
f[u] = 1LL * W[u] * L;
continue;
}
root[u] = 0;
long long sum_f = 0;
for (int v : children[u]) {
root[u] = merge(root[u], root[v], 1, M);
sum_f += f[v];
}
long long Ku = 1LL * (children[u].size() - 1) * L;
int idx_minus = idx_minus_W[u];
long long mass_lt = query_mass(root[u], 1, M, 1, idx_minus - 1);
long long pL_lt = query_p_mass(root[u], 1, M, 1, idx_minus - 1);
f[u] = sum_f + 1LL * W[u] * Ku + 1LL * W[u] * mass_lt + pL_lt;
if (Delta <= Ku) {
root[u] = 0;
if (Delta > 0) add_mass(root[u], 1, M, idx_minus, Delta);
} else {
long long target = Delta - Ku;
keep_prefix(root[u], 1, M, target);
long long mass_le = query_mass(root[u], 1, M, 1, idx_minus);
clear_range(root[u], 1, M, 1, idx_minus);
if (Ku + mass_le > 0) {
add_mass(root[u], 1, M, idx_minus, Ku + mass_le);
}
int idx_plus = idx_plus_W[u];
if (idx_plus < M) {
long long mass_ge = query_mass(root[u], 1, M, idx_plus + 1, M);
clear_range(root[u], 1, M, idx_plus + 1, M);
if (mass_ge > 0) {
add_mass(root[u], 1, M, idx_plus, mass_ge);
}
}
}
}
long long ans = f[0] + query_p_mass(root[0], 1, M, 1, idx_0 - 1);
return ans;
}
