#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int MAXN = 200005;
int N, Q;
long long W[MAXN];
vector<int> children[MAXN];
int d_deg[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];
d_deg[i] = 0;
}
for (int i = 1; i < N; i++) {
children[P[i]].push_back(i);
d_deg[P[i]]++;
}
}
// 询问函数
long long query(int L_in, int R_in) {
long long L = L_in;
long long R = R_in;
vector<map<long long, long long>> M(N);
vector<long long> V(N, 0);
// 自底向上进行树形 DP
for (int u = N - 1; u >= 0; u--) {
int k = d_deg[u];
// 若为叶子节点
if (k == 0) {
V[u] = L * W[u];
M[u][W[u]] = R - L;
continue;
}
// 启发式合并 (Small-to-Large Merge)
int heavy = -1;
int max_size = -1;
for (int v : children[u]) {
V[u] += V[v];
if ((int)M[v].size() > max_size) {
max_size = M[v].size();
heavy = v;
}
}
swap(M[u], M[heavy]);
for (int v : children[u]) {
if (v == heavy) continue;
for (auto const& [val, mass] : M[v]) {
M[u][val] += mass;
}
M[v].clear();
}
// 截断所有 < -W[u] 的斜率，并将它们移动至 -W[u]
long long mass_less = 0;
while (!M[u].empty()) {
auto it = M[u].begin();
if (it->first < -W[u]) {
mass_less += it->second;
// 计算移动质量导致的代价偏移
V[u] += it->second * (it->first + W[u]);
M[u].erase(it);
} else {
break;
}
}
if (mass_less > 0) M[u][-W[u]] += mass_less;
// 截断所有 > W[u] 的斜率，并将它们移动至 W[u]
long long mass_greater = 0;
while (!M[u].empty()) {
auto it = prev(M[u].end());
if (it->first > W[u]) {
mass_greater += it->second;
M[u].erase(it);
} else {
break;
}
}
if (mass_greater > 0) M[u][W[u]] += mass_greater;
// 在最左端加入当前节点自身的质量约束
M[u][-W[u]] += 1LL * (k - 1) * L;
V[u] += 1LL * (k - 1) * L * W[u];
// 移除多余的质量，保持总质量平衡
long long rem = 1LL * (k - 1) * R;
while (rem > 0 && !M[u].empty()) {
auto it = prev(M[u].end());
if (it->second <= rem) {
rem -= it->second;
M[u].erase(it);
} else {
it->second -= rem;
rem = 0;
}
}
}
// 统计根节点最终的最小代价值
long long ans = V[0];
for (auto const& [val, mass] : M[0]) {
if (val < 0) {
ans += val * mass;
} else {
break;
}
}
return ans;
}
