#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<int> adj[200200];
ll a[200200];
void init(std::vector<int> P, std::vector<int> W) {
n = P.size();
for (int i=1;i<n;i++) adj[P[i]+1].push_back(i+1);
for (int i=0;i<n;i++) a[i+1] = W[i];
}
ll ofs[200200];
multiset<array<ll, 2>> dp[200200];
void merge(int s, int v){
ofs[s] += ofs[v];
if (dp[s].size() < dp[v].size()) swap(dp[s], dp[v]);
for (auto &p:dp[v]) dp[s].insert(p);
}
void dfs(int s, int L, int R){
dp[s].clear();
ofs[s] = 0;
if (adj[s].empty()){
ofs[s] = a[s] * L;
dp[s].insert({0, R-L});
return;
}
for (auto &v:adj[s]){
dfs(v, L, R);
merge(s, v);
}
int d = adj[s].size();
ll len = (ll)d * (R-L);
while(!dp[s].empty() && (*prev(dp[s].end()))[0] > a[s]){
len -= (*prev(dp[s].end()))[1];
dp[s].erase(prev(dp[s].end()));
}
dp[s].insert({a[s], (ll)d*R - L - len});
len = (ll)d*R - L;
while(len > R-L){
auto [dy, cnt] = *dp[s].begin();
dp[s].erase(dp[s].begin());
ofs[s] += dy * cnt;
len -= cnt;
if (len >= R-L) continue;
ofs[s] -= dy * ((R-L) - len);
dp[s].insert({dy, (R-L) - len});
len = R-L;
break;
}
}
long long query(int L, int R) {
dfs(1, L, R);
return ofs[1];
}
