#include<iostream>
#include<vector>
#include<algorithm>
#include "tree.h"
using namespace std;
vector<int> w;
vector<pair<int,int>> children;
vector<vector<int>> adj_list;
int n;
void init(std::vector<int> P, std::vector<int> W){
swap(W,w);
n = P.size();
adj_list.assign(P.size(),{});
for(int i = 0; i < P.size(); i ++){
if(P[i] != -1){
adj_list[P[i]].push_back(i);
}
}
for(int i = 0; i < P.size(); i++){
children.push_back({adj_list[i].size(),i});
}
sort(children.begin(),children.end());
}
long long query(int L, int R){
long long answer = 0;
vector<long long> sum(n);
for(int i = 0; i < n; i++){
if(children[i].first == 0){
answer += (L * w[children[i].second]);
sum[children[i].second] = L;
}
else{
long long total = 0;
int u = children[i].second;
for(int j = 0; j < children[i].first; j++){
total += sum[adj_list[u][j]];
}
if(total < R){
answer += (0*w[children[i].second]);
sum[children[i].second] = total;
}
else{
int diff = R - total;
answer += (abs(diff)*w[children[i].second]);
sum[children[i].second] = total + diff;
}
}
}
return answer;
}
