#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
vector<int> P_global;
vector<int> W_global;
vector<vector<int>> children;
vector<int> leaves;
long long sum_leaves_W = 0;
void init(std::vector<int> P, std::vector<int> W) {
n = P.size();
P_global = P;
W_global = W;
children.assign(n, vector<int>());
vector<int> deg(n, 0);
for (int i = 1; i < n; ++i) {
children[P[i]].push_back(i);
deg[P[i]]++;
}
for (int i = 0; i < n; ++i) {
if (deg[i] == 0) {
leaves.push_back(i);
sum_leaves_W += W[i];
}
}
}
long long query(int L, int R) {
// 提取所有不同的权重作为关键事件点 (离散化 t)
vector<int> events;
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());
// 对于特殊情况 W[i] <= 1
if (events.back() <= 1) {
vector<long long> f(n, 0);
long long total_G = 0;
for (int i = n - 1; i >= 0; --i) {
if (children[i].empty()) {
f[i] = L;
} else {
long long sum_c = 0;
for (int v : children[i]) {
sum_c += f[v];
}
f[i] = min((long long)R, max((long long)L, sum_c));
if (W_global[i] > 0) {
total_G += max(0LL, sum_c - R) * W_global[i];
}
}
}
return L * sum_leaves_W + total_G;
}
// 按 W[i] 对节点分组
vector<vector<int>> nodes_at_W(events.size());
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);
}
vector<long long> f(n, L);
vector<long long> delta(n, 0);
vector<bool> active(n, false);
long long total_integral = 0;
// 我们从无穷大降到 0，逐步激活节点并维护树上的状态
for (int idx = (int)events.size() - 1; idx > 0; --idx) {
int t_high = events[idx];
int t_low = events[idx - 1];
int duration = t_high - t_low;
for (int u : nodes_at_W[idx]) {
active[u] = true;
if (children[u].empty()) {
delta[u] = 0;
f[u] = L;
} else {
long long s = 0;
for (int v : children[u]) s += f[v];
delta[u] = s;
f[u] = min((long long)R, max((long long)L, delta[u]));
}
// 向上更新祖先节点
int curr = P_global[u];
while (curr != -1 && active[curr]) {
long long s = 0;
for (int v : children[curr]) s += f[v];
if (s == delta[curr]) break; // 没变化就提前停止 (剪枝)
delta[curr] = s;
f[curr] = min((long long)R, max((long long)L, delta[curr]));
curr = P_global[curr];
}
}
// 累积积分 G(t)
long long current_G = 0;
for (int i = 0; i < n; ++i) {
if (active[i] && delta[i] > R) {
current_G += (delta[i] - R);
}
}
total_integral += current_G * duration;
}
return L * sum_leaves_W + total_integral;
}
