#include "tree.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int n;
vector<vector<int>> adj;
vector<ll> w;
void init(std::vector<int> P, std::vector<int> W) {
n = P.size();
adj.resize(n);
w.resize(n);
for(int i = 0; i<n; i++) w[i] = W[i];
for(int i = 1; i<n; i++) adj[P[i]].push_back(i);
}
long long query(int L, int R) {
ll r = R; ll l = L;
ll sol = 0;
vector<int> sz(n, 0);
function<map<ll, ll>(int)> dfs = [&](int v)->map<ll, ll>{
map<ll, ll> mp;
if(!adj[v].size()){
sol += w[v]*l;
sz[v] = l;
return mp;
}
for(int u: adj[v]){
auto tmp = dfs(u);
sz[v] += sz[u];
if(tmp.size() > mp.size()) swap(mp, tmp);
for(auto [k, vaal]: tmp){
mp[k] += vaal;
}
}
if(sz[v] <= r){
if(sz[v]-l > 0) mp[w[v]] += sz[v]-l;
return mp;
}
for(auto& [k, val]: mp){
if(k >= w[v]) break;
ll vl = min(sz[v]-r, val);
sz[v] -= vl;
sol += vl*k;
if(vl == val) mp.erase(k);
else mp[k] -= vl;
if(sz[v] <= r) break;
}
ll vl = sz[v]-r;
sz[v] -= vl;
sol += vl*w[v];
if(r>l) mp[w[v]] += r-l;
return mp;
};
dfs(0);
return sol;
}
