#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> P_global;
vector<int> W_global;
vector<int> deg;
vector<int> events;
vector<vector<int>> nodes_at_W;
int num_events;
long long sum_leaves_W;
// 使用一维原生数组结合局部连续内存保证极致的缓存命中率和自动向量化
long long f_arr[200005];
long long S_arr[200005];
bool active_arr[200005];
void init(std::vector<int> P, std::vector<int> W) {
n = P.size();
P_global = P;
W_global = W;
events.clear();
nodes_at_W.clear();
deg.assign(n, 0);
sum_leaves_W = 0;
// 统计度数并获取叶子节点的固定开销
for (int i = 1; i < n; ++i) {
deg[P_global[i]]++;
}
for (int i = 0; i < n; ++i) {
if (deg[i] == 0) {
sum_leaves_W += W_global[i];
}
}
// 提取并离散化所有事件点 W
events.push_back(0);
for (int i = 0; i < n; ++i) {
events.push_back(W_global[i]);
}
sort(events.begin(), events.end());
events.erase(unique(events.begin(), events.end()), events.end());
num_events = events.size();
// 建立事件倒排索引
nodes_at_W.assign(num_events, vector<int>());
for (int i = 0; i < n; ++i) {
int idx = lower_bound(events.begin(), events.end(), W_global[i]) - events.begin();
nodes_at_W[idx].push_back(i);
}
}
long long query(int L, int R) {
long long current_G = 0;
long long total_integral = 0;
long long LL_L = L;
long long LL_R = R;
// 被彻底拆分的扁平循环重置，极大概率被编译器识别并转化为高速内存填充汇编 (AVX2 / memset 等)
for(int i = 0; i < n; ++i) f_arr[i] = LL_L;
for(int i = 0; i < n; ++i) S_arr[i] = 1LL * deg[i] * LL_L;
for(int i = 0; i < n; ++i) active_arr[i] = false;
// 倒序处理时间事件
for (int idx = num_events - 1; idx > 0; --idx) {
long long duration = events[idx] - events[idx - 1];
for (int u : nodes_at_W[idx]) {
active_arr[u] = true; // 状态转为活跃
if (S_arr[u] > LL_R) {
current_G += (S_arr[u] - LL_R);
}
long long old_f = f_arr[u];
long long val = S_arr[u];
if (val < LL_L) val = LL_L; // 限定传递的值必然落在 [L, R] 间
if (val > LL_R) val = LL_R;
f_arr[u] = val;
long long diff = f_arr[u] - old_f;
int curr = u;
// 顺着树形结构向上冒泡只携带改变的影响值，均摊极小
while (diff > 0) {
int p = P_global[curr];
if (p == -1) break;
long long old_S = S_arr[p];
S_arr[p] += diff;
if (!active_arr[p]) {
// 若向上的祖先尚未处于活跃范围，它自身仍稳定反馈 L 给上级，终止传播即可
break;
}
// 仅更新并维护超额部分的代价积分
long long old_val = (old_S > LL_R) ? (old_S - LL_R) : 0;
long long new_val = (S_arr[p] > LL_R) ? (S_arr[p] - LL_R) : 0;
current_G += (new_val - old_val);
long long old_fp = f_arr[p];
long long vp = S_arr[p];
if (vp < LL_L) vp = LL_L;
if (vp > LL_R) vp = LL_R;
f_arr[p] = vp;
diff = f_arr[p] - old_fp;
curr = p;
}
}
// 矩形积分累加
total_integral += current_G * duration;
}
return LL_L * sum_leaves_W + total_integral;
}
