#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
#include "tree.h"
const int N = 1e5+5432, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;
struct Element
{
ll val,su;
bool operator < (const Element &element) const
{
return val < element.val;
}
};
ll n,q,l,r,res;
vector<ll> G[N];
multiset<Element> us[N];
ll su_us[N], C[N];
std::vector<int> p, w;
void DFS(int v)
{
su_us[v] = 0, us[v].clear(), C[v] = 0;
for(auto x : G[v])
{
if(x == p[v]) continue;
DFS(x);
su_us[v] += su_us[x], C[v] += C[x];
for(auto it = us[x].begin(); it != us[x].end(); ++it) us[v].insert(*it);
}
if(C[v] == 0)
{
C[v] = l, res += C[v]*abs(w[v]), us[v].insert({w[v],r-l}), su_us[v] += r-l;
}
else
{
us[v].insert({w[v],(ll)2e6}), su_us[v] += (ll)2e6;
while(C[v] > r)
{
int roz = C[v]-r;
Element at = *us[v].begin();
us[v].erase(us[v].find(at));
if(at.su <= roz)
{
C[v] -= at.su, res += at.val*at.su;
}
else
{
C[v] -= roz, res += at.val*roz;
us[v].insert({at.val,at.su-roz});
}
}
}
}
void init(std::vector<int> P, std::vector<int> W) {
p = P;
w = W;
n = (int)p.size();
for(int i = 1; i < n; ++i)
{
G[p[i]].pb(i);
}
}
long long query(int L, int R) {
res = 0, l = L, r = R;
DFS(0);
return res;
}
