#pragma GCC optimize("Ofast,unroll-loops")
#include "tree.h"
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll INF = 2e9;
const ll MOD = 998244353;
int n;
vector<int> p, w;
vector<vector<int>> A;
void init(vector<int> P, vector<int> W) {
p = P; w = W; n = (int)p.size();
A.resize(n); for (ll i=1; i<n; i++){
A[p[i]].push_back(i);
}
}
pair<pair<ll, ll>, map<ll, ll>> dfs(ll u, ll l, ll r){
map<ll, ll> rems; ll cval=0, res=0;
if (A[u].empty()){
return {{w[u]*l, l}, rems};
}else{
for (auto v:A[u]){
auto ret = dfs(v, l, r);
cval+=ret.ff.ss; res+=ret.ff.ff;
for (auto [x, y]:ret.ss){
rems[x]+=y;
}
}
if (cval>r){
while (cval>r and !rems.empty() and w[u]>(*rems.begin()).ff){
ll con = min(cval-r, (*rems.begin()).ss);
cval-=con; res+=con*((*rems.begin()).ff);
if ((*rems.begin()).ss==con){
rems.erase(rems.begin());
}else{
rems[(*rems.begin()).ff]-=con;
}
}
if (cval>r){
ll con=cval-r; cval-=con; res+=w[u]*con;
}
}
rems[w[u]]+=cval-l; ll cap = cval-l;
map<ll, ll> arems; ll csum=0;
for (auto [x, y]:rems){
if (csum==cap) break;
ll add = min(y, cap-csum);
arems[x]+=add; csum+=add;
}
return {{res, cval}, arems};
}
}
long long query(int L, int R) {
auto res = dfs(0, L, R);
return res.ff.ff;
}
