#include <bits/stdc++.h>
#include "tree.h"
#define ll long long
#define endl "\n"
using namespace std;
const ll N = 2e5 + 5;
ll t[N];
void upd(ll i, ll d)
{
for (; i < N; i |= (i + 1)) t[i] += d;
}
ll sum(ll i)
{
ll ans = 0;
for (; i >= 0; i = (i & (i + 1)) - 1) ans += t[i];
return ans;
}
ll sum(ll l, ll r)
{
return sum(r) - sum(l - 1);
}
int n;
vector<ll> g[N];
ll val[N], d[N], f[N];
ll l, r, timer = 0;
std::vector<int> p, w;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> s[N];
set<pair<ll, ll>> del;
void init(ll v)
{
d[v] = ++timer;
for (ll to : g[v])
init(to);
f[v] = timer;
}
ll dfs(ll v)
{
ll ans = 0;
if (g[v].size() == 0) upd(d[v], l), ans += l * w[v];
while (!s[v].empty())
s[v].pop();
for (ll to : g[v])
{
ans += dfs(to);
if (s[to].size() > s[v].size())
swap(s[to], s[v]);
while (!s[to].empty())
s[v].push(s[to].top()), s[to].pop();
}
s[v].push(make_pair(w[v], v));
while ((val[v] = sum(d[v], f[v])) > r)
{
auto [x, to] = s[v].top();
val[to] = sum(d[to], f[to]);
s[v].pop();
auto it = del.upper_bound(make_pair(d[to], 1e9));
if (it != del.begin())
{
it--;
if (it->second >= f[to]) continue;
}
ll tmp = min(val[to] - l, val[v] - r);
ans += tmp * x;
upd(d[to], -tmp);
if ((val[to] = sum(d[to], f[to])) > l) s[v].push(make_pair(x, to));
else del.insert(make_pair(d[to], f[to]));
}
return ans;
}
void init(std::vector<int> P, std::vector<int> W)
{
p = P;
n = p.size();
w = W;
w.insert(w.begin(), 0);
p.insert(p.begin(), 0);
for (ll i = 1; i <= n; i++)
{
p[i]++;
g[p[i]].push_back(i);
}
init(1);
}
long long query(int L, int R)
{
l = L;
r = R;
for (ll i = 1; i <= n; i++) t[i] = 0;
del.clear();
return dfs(1);
}
