#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"
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const int N = 2e5+5432, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;
struct Element
{
ll val,su;
bool operator < (const Element &element) const
{
if(val == element.val) return su < element.su;
return val < element.val;
}
};
ll n,q,l,r,res;
vector<ll> G[N];
multiset<Element> us[N];
ll su_us[N], C[N], idx[N];
std::vector<int> p, w;
void merguj(ll a, ll b)
{
if((int)us[idx[a]].size() < (int)us[idx[b]].size())
{
su_us[idx[b]] += su_us[idx[a]];
for(auto it = us[idx[a]].begin(); it != us[idx[a]].end(); ++it) us[idx[b]].insert(*it);
idx[a] = idx[b];
}
else
{
su_us[idx[a]] += su_us[idx[b]];
for(auto it = us[idx[b]].begin(); it != us[idx[b]].end(); ++it) us[idx[a]].insert(*it);
}
}
ll cnt = -1;
void DFS(int v)
{
C[v] = 0, idx[v] = -1;
for(auto x : G[v])
{
DFS(x);
C[v] += C[x];
if(idx[v] == -1)
{
idx[v] = idx[x];
}
else merguj(v,x);
}
if(C[v] == 0)
{
C[v] = l, res += C[v]*w[v], ++cnt, su_us[cnt] = 0, idx[v] = cnt, us[cnt].clear();
}
else
{
us[idx[v]].insert({w[v],(ll)2e12}), su_us[idx[v]] += (ll)2e12;
while(C[v] > r)
{
ll roz = C[v]-r;
Element at = *us[idx[v]].begin();
us[idx[v]].erase(us[idx[v]].find(at));
if(at.su <= roz)
{
C[v] -= at.su, su_us[idx[v]] -= at.su, res += at.val*at.su;
}
else
{
C[v] -= roz, su_us[idx[v]] -= roz, res += at.val*roz;
us[idx[v]].insert({at.val,at.su-roz});
}
}
while(su_us[idx[v]] > C[v]-l)
{
ll roz = su_us[idx[v]]-(C[v]-l);
Element at = *us[idx[v]].rbegin();
us[idx[v]].erase(us[idx[v]].find(at));
if(at.su <= roz)
{
su_us[idx[v]] -= at.su;
}
else
{
su_us[idx[v]] -= roz, us[idx[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, cnt=-1;
DFS(0);
return res;
}
