#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;
}
for(auto itr: ch[node]){
sub[node] += sub[itr];
for(auto j: relax[itr]){
relax[node].insert(j);
}
}
relax[node].insert({w[node], node});
while(sub[node] > R){
auto best = *relax[node].begin();
long long cnt = sub[best.second] - L;
cnt = min(cnt, sub[node] - R);
c[best.second] -= cnt;
sub[best.second] -= cnt;
int up = best.second;
while(up != node){
up = p[up];
sub[up] -= cnt;
}
if(sub[best.second] == L){
relax[node].erase(relax[node].find(best));
}
}
}
long long ans = 0;
for(int i = 0; i < n; i++){
ans += abs(c[i]) * w[i];
}
return ans;
}
