#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
std::vector<int> p, w;
ll maxi = 404040;
vector<vector<ll>>g(maxi);
const ll mx = 404042;
ll a[mx];
ll st[4*mx];
vector<ll>lazy(mx, -1);
void push(ll l, ll r, ll v)
{
if (lazy[v]==-1) return;
st[v] = lazy[v]*(r-l+1);
if (l!=r)
{
lazy[2*v] = lazy[v];
lazy[2*v+1] = lazy[v];
}
lazy[v] = -1;
}
ll getsum (ll l, ll r, ll v, ll ql, ll qr)
{
push(l, r, v);
if (r<ql or l>qr)
return 0;
if (l>=ql and r<=qr)
return st[v];
ll mid = (l+r)/2;
return getsum(l, mid, 2*v, ql, qr) + getsum(mid+1, r, 2*v+1, ql, qr);
}
void update(ll l, ll r, ll v, ll ql, ll qr, ll val)
{
if (r<ql or l>qr)
return;
push(l, r, v);
if (l>=ql and r<=qr)
{
lazy[v] = val;
push(l, r, v);
return;
}
ll mid = (l+r)/2;
update(l, mid, 2*v, ql, qr, val);
update(mid+1, r, 2*v+1, ql, qr, val);
st[v] = st[2*v]+st[2*v+1];
}
vector<ll>fen(maxi, 0);
void add(ll x, ll val)
{
while (x<maxi)
{
fen[x] += val;
x += x&-x;
}
}
ll sum(ll l, ll r)
{
if (l!=1) return sum(1, r) - sum(1, l-1);
ll res = 0;
while (r>0)
{
res += fen[r];
r -= r&-r;
}
return res;
}
vector<multiset<pair<ll,ll>>>ms(maxi);
vector<ll>tin(maxi), tout(maxi);
ll t = 0;
void dfs1(ll x, ll p)
{
tin[x] = ++t;
for (auto i:g[x])
{
if (i!=p)
dfs1(i, x);
}
tout[x] = ++t;
}
void init(std::vector<int> P, std::vector<int> W) {
p = P;
w.push_back(0);
for (auto i:W) w.push_back(i);
n = (int)p.size();
for (int i=2 ; i<=n ; i++)
{
g[i].push_back(p[i]+1);
g[p[i]+1].push_back(i);
}
dfs1(1, 0);
}
ll res = 0;
ll l, r;
void dfs(ll x, ll p)
{
if (x!=1 and g[x].size()==1)
{
add(x, l);
res += l*w[x];
}
ll sm=0;
for (auto i:g[x])
{
if (i!=p)
{
dfs(i, x);
sm += sum(tin[i], tout[i]);
if (ms[i].size()>ms[x].size()) swap(ms[x], ms[i]);
for (auto j:ms[i]) ms[x].insert(j);
}
}
ms[x].insert({w[x], x});
while (true)
{
ll vv = sum(tin[x], tout[x]);
if (vv<=r) break;
auto it = *ms[x].begin();
ll id = it.second;
ms[x].erase(ms[x].begin());
if (getsum(1, maxi, 1, tin[id], tin[id])==1) continue;
ll to = sum(tin[id], tout[id]);
ll hw = min(vv-r, to-l);
res += hw*w[id];
add(id, -hw);
if (to-hw==l)
{
update(1, maxi, 1, tin[id], tout[id], 1);
}
else
{
ms[x].insert({w[id], id});
}
}
}
long long query(int L, int R) {
l = L;
r = R;
res = 0;
dfs(1, 0);
for (int i=1 ;i<maxi ; i++)
{
fen[i] = 0;
ms[i].clear();
}
update(1, maxi, 1, 1, maxi, 0);
return res;
}
