#include "bits/stdc++.h"
#include "tree.h"
using namespace std;
#define pb push_back
int n;
vector<long long> p, w, order;
vector<vector<int> > ch;
void dfs(int node){
for(auto itr: ch[node]){
dfs(itr);
}
order.pb(node);
}
void init(vector<int> P, vector<int> W) {
n = (int)P.size();
p.resize(n);
w.resize(n);
for(int i = 0; i < n; i++){
w[i] = W[i];
p[i] = P[i];
}
ch.resize(n);
for(int i = 1; i < n; i++){
ch[P[i]].pb(i);
}
dfs(0);
}
long long query(int L, int R){
vector<long long> c(n), sub(n);
set<pair<long long, long long> > relax[n];
for(int i = 0; i < n; i++){
int node = order[i];
if(!ch[node].size()){
c[node] = L; // leafler L olacak kalanlar <= 0
sub[node] = L;
continue;
}
long long mysub = 0;
for(auto itr: ch[node]){
mysub += sub[itr];
for(auto j: relax[itr]){
relax[node].insert(j);
}
}
while(relax[node].size() > 0 && mysub > R){
auto best = *relax[node].begin();
if(best.first > w[node]) break; // beni degistirmek daha iyi
long long cnt = sub[best.second] - L;
cnt = min(cnt, mysub - R);
mysub -= cnt;
int ft = best.second;
c[ft] -= cnt;
while(ft != node){
sub[ft] -= cnt;
ft = p[ft];
}
if(cnt == sub[best.second] - L){
relax[node].erase(relax[node].find(best));
}
}
if(mysub > R){
c[node] = R - mysub;
}
sub[node] = mysub + c[node];
relax[node].insert({w[node], node});
}
long long ans = 0;
for(int i = 0; i < n; i++){
ans += abs(c[i]) * w[i];
}
return ans;
}
