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