#include "tree.h"
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int n;
int par[202020];
vector<int> child[202020];
ll w[202020];
void init(vector<int> P, vector<int> W) {
n = (int)P.size();
for (int i = 0; i < n; i++) {
par[i] = P[i];
child[par[i]].push_back(i);
}
for (int i = 0; i < n; i++) w[i] = W[i];
}
ll dp[202020], sum[202020];
typedef priority_queue<pll, vector<pll>, greater<pll>> pq;
pq solve(int v, ll L, ll R) {
pq plus;
if (child[v].size() == 0) {
dp[v] += L * w[v];
sum[v] = L;
return plus;
}
for (int u : child[v]) {
pq t = solve(u, L, R);
if (plus.size() < t.size()) swap(plus, t);
while (!t.empty()) {
plus.push(t.top());
t.pop();
}
dp[v] += dp[u];
sum[v] += sum[u];
}
while (!plus.empty() && sum[v] > R) {
pll t = plus.top();
if (t.first >= w[v]) break;
plus.pop();
if (sum[v] - R < t.second) {
dp[v] += (sum[v] - R) * t.first;
sum[v] -= (sum[v] - R);
plus.push({t.first, t.second - (sum[v] - R)});
}
else {
dp[v] += t.second * t.first;
sum[v] -= t.second;
}
}
if (sum[v] > R) {
dp[v] += (sum[v] - R) * w[v];
sum[v] -= (sum[v] - R);
}
if (sum[v] > L) plus.push({w[v], sum[v] - L});
return plus;
}
long long query(int L, int R) {
for (int i = 0; i < n; i++) sum[i] = dp[i] = 0;
solve(0, L, R);
return dp[0];
}
