#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 200005;
int N, M, Q;
long long W[MAXN];
int P_arr[MAXN];
vector<int> children[MAXN];
bool w_le_1 = true;
// O(N) DP Array states for W <= 1
long long sum_dp_0[MAXN];
long long sum_dp_1[MAXN];
long long sum_dp_2[MAXN];
long long dp_0[MAXN];
long long dp_1[MAXN];
long long dp_2[MAXN];
// Segment tree node
struct Node {
int lc, rc;
long long mass, p_mass;
} tr[8000000];
int node_cnt = 0;
int stack_nodes[8000000];
int top_idx = 0;
inline int new_node() {
int u = top_idx ? stack_nodes[--top_idx] : ++node_cnt;
tr[u].lc = tr[u].rc = 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;
stack_nodes[top_idx++] = v;
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);
stack_nodes[top_idx++] = v; // Memory reuse for optimized execution
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 idx_minus_W[MAXN];
int idx_plus_W[MAXN];
int idx_0;
long long f[MAXN];
int root[MAXN];
void init(std::vector<int> P, std::vector<int> W_in) {
N = W_in.size();
for (int i = 0; i < N; i++) {
W[i] = W_in[i];
P_arr[i] = P[i];
if (W[i] > 1) w_le_1 = false;
}
for (int i = 1; i < N; i++) children[P[i]].push_back(i);
if (!w_le_1) {
std::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]);
}
std::sort(vals.begin(), vals.end());
vals.erase(std::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 = std::lower_bound(P_val + 1, P_val + M + 1, 0LL) - P_val;
for (int i = 0; i < N; i++) {
idx_minus_W[i] = std::lower_bound(P_val + 1, P_val + M + 1, -W[i]) - P_val;
idx_plus_W[i] = std::lower_bound(P_val + 1, P_val + M + 1, W[i]) - P_val;
}
}
}
long long query(int L, int R) {
if (w_le_1) { // 针对 W <= 1 的高频询问进行 O(N) O3 极致常数压榨
long long LL = L, RR = R;
std::memset(sum_dp_0, 0, N * sizeof(long long));
std::memset(sum_dp_1, 0, N * sizeof(long long));
std::memset(sum_dp_2, 0, N * sizeof(long long));
for (int u = N - 1; u >= 0; u--) {
long long s0 = sum_dp_0[u], s1 = sum_dp_1[u], s2 = sum_dp_2[u];
int w = W[u];
long long d0, d1, d2;
if (w == 0) {
d0 = LL + s1;
d1 = s1;
d2 = -RR + s1;
} else {
long long mx, c;
mx = s0;
c = LL + s1; if (c > mx) mx = c;
c = (LL << 1) + s2; if (c > mx) mx = c;
d0 = mx;
mx = -RR + s0;
c = s1; if (c > mx) mx = c;
c = LL + s2; if (c > mx) mx = c;
d1 = mx;
mx = -(RR << 1) + s0;
c = -RR + s1; if (c > mx) mx = c;
c = s2; if (c > mx) mx = c;
d2 = mx;
}
dp_0[u] = d0; dp_1[u] = d1; dp_2[u] = d2;
int pu = P_arr[u];
if (pu >= 0) {
sum_dp_0[pu] += d0;
sum_dp_1[pu] += d1;
sum_dp_2[pu] += d2;
}
}
return dp_1[0];
} else { // 针对任意权重的离散化建树处理 (涵盖 Subtask 1,2,3)
node_cnt = 0;
top_idx = 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;
}
}
