#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N = 200200;
int n;
std::vector<int> w, p;
vector<int> adj[N];
ll res;
ll sum[N];
vector<int> dfs(int v, ll l, ll r) {
if (adj[v].empty()) {
sum[v] = l;
res += l;
return {v};
}
vector<int> sub{v};
sum[v]=0;
for (int u : adj[v]) {
auto vec = dfs(u, l, r);
sum[v] += sum[u];
for (int x : vec) sub.pb(x);
}
if (sum[v] <= r) return sub;
sort(sub.begin(), sub.end(), [&](int i, int j) {
return w[i] < w[j];
});
for (int x : sub) {
int save_x = x;
ll mn = sum[v] - r;
while (x != v) {
mn = min(mn, sum[x] - l);
x = p[x];
}
x = save_x;
res += mn * w[x];
while (x != v) {
sum[x] -= mn;
x = p[x];
}
assert(v==x);
sum[x] -= mn;
}
return sub;
}
void init(std::vector<int> P, std::vector<int> W) {
p = P;
w = W;
n = W.size();
for (int i=1; i<n; i++) adj[P[i]].pb(i);
}
long long query(int L, int R) {
res = 0;
dfs(0, L, R);
return res;
}
