#include "tree.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<map>
#include<vector>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
namespace{
int n;
vector<vector<int>> graph;
vector<int> p;
vector<ll> vec, dp;
vector<int> ids;
ll l, r, ans = 0;
void dfs(int node, int parent){
for(auto &x: graph[node]){
if(x == parent) continue;
dfs(x, node);
dp[node] += dp[x];
}
if((int)graph[node].size() == 1 && node != 1){
dp[node] = l;
ans += l * vec[node];
}
}
}
void init(std::vector<int> P, std::vector<int> W) {
n = (int)P.size();
graph.resize(n + 1);
vec.resize(n + 1);
dp.resize(n + 1);
p.resize(n + 1);
for(int i = 1; i < n; i++){
graph[i + 1].push_back(P[i] + 1);
graph[P[i] + 1].push_back(i + 1);
p[i + 1] = P[i] + 1;
}
p[1] = 1;
for(int i = 1; i <= n; i++) vec[i] = W[i - 1];
ids.resize(n + 1);
for(int i = 1; i <= n; i++) ids[i] = i;
auto cmp = [&](int a, int b){
return vec[a] < vec[b];
};
sort(next(ids.begin()), ids.end(), cmp);
}
long long query(int L, int R) {
l = L;
r = R;
fill(dp.begin(), dp.end(), 0);
ans = 0;
dfs(1, 0);
for(int ord = 1; ord <= n; ord++){
int node = ids[ord];
ll mini = dp[node], maxi = dp[node];
int cur = node;
while(cur != 1){
cur = p[cur];
mini = min(mini, dp[cur]);
maxi = max(maxi, dp[cur]);
}
if(maxi <= r) continue;
ll sub = min(maxi - r, mini - l);
ans += sub * vec[node];
cur = node;
dp[node] -= sub;
while(cur != 1){
cur = p[cur];
dp[cur] -= sub;
}
}
return ans;
}
