#include "tree.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int n;
vector<signed> p;
vector<int> w;
vector<vector<int>> child;
int sum=0;
void init(std::vector<signed> P, std::vector<signed> W) {
p=P;
n = (int)p.size();
w.resize(n);
for (int i = 0; i < n; i++)
{
w[i]=W[i];
}
child.resize(n);
for (int i = 1; i < n; i++)
{
child[p[i]].push_back(i);
}
}
pair<int,vector<pair<int,int>>> dfs(int x, int l, int r){
if(sz(child[x])==0){
sum+=l*w[x];
return {l,{{w[x],l}}};
}
vector<pair<int,int>> tot;
int sm=0;
for (auto u : child[x])
{
pair<int,vector<pair<int,int>>> d=dfs(u,l,r);
vector<pair<int,int>> cu=d.second;
sm+=d.first;
for (int i = 0; i < sz(cu); i++) tot.push_back(cu[i]);
}
sort(all(tot));
for (int i = 0; i < sz(tot); i++) {
if(tot[i].first>=w[x]){
int mn=max(0LL,sm-r);
sm-=mn;
sum+=mn*w[x];
break;
}
int mn=max(0LL,min(tot[i].second-l,sm-r));
sm-=mn;
tot[i].second-=mn;
sum+=mn*tot[i].first;
}
if(sm>0){
int mn=max(0LL,sm-r);
sm-=mn;
sum+=mn*w[x];
}
tot.push_back({w[x],sm});
return {sm,tot};
}
long long query(signed L, signed R) {
sum=0;
dfs(0,L,R);
return sum;
}
