#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 2e5 + 5;
int n;
arr<vec<int>, N> ch;
arr<int, N> wg;
int nm;
arr<int, N> st, fn, rv;
void st_dfs(int u = 1) {
st[u] = ++nm, rv[nm] = u;
for (int v : ch[u]) st_dfs(v);
fn[u] = nm;
}
void init(vec<sig> _pr, vec<sig> _wg) {
n = _pr.size();
for (int u = 1; u <= n; u++)
ch[_pr[u - 1] + 1].push_back(u);
for (int u = 1; u <= n; u++)
wg[u] = _wg[u - 1];
st_dfs();
// for (int u = 1; u <= n; u++)
// cout << u << ": " << st[u] << " " << fn[u] << '\n';
}
struct Vl {
arr<int, 4 * N> tr;
void intl() {
tr.fill(0);
}
void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
if (lw == hg) { tr[u] += x; return; }
int md = (lw + hg) / 2;
if (i <= md) upd(i, x, 2 * u, lw, md);
else upd(i, x, 2 * u + 1, md + 1, hg);
tr[u] = tr[2 * u] + tr[2 * u + 1];
}
int qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
if (l <= lw && hg <= r) return tr[u];
int md = (lw + hg) / 2, ans = 0;
if (l <= md) ans += qry(l, r, 2 * u, lw, md);
if (r > md) ans += qry(l, r, 2 * u + 1, md + 1, hg);
return ans;
}
int cnt(int u = 1, int lw = 1, int hg = n) {
if (lw == hg) return wg[rv[lw]] * abs(tr[u]);
int md = (lw + hg) / 2;
return cnt(2 * u, lw, md) + cnt(2 * u + 1, md + 1, hg);
}
} vl;
struct Rm {
arr<int, 4 * N> tr;
void intl() {
tr.fill(0);
}
void upd(int l, int r, int x, int u = 1, int lw = 1, int hg = n) {
if (l <= lw && hg <= r) { tr[u] += x; return; }
int md = (lw + hg) / 2;
if (l <= md) upd(l, r, x, 2 * u, lw, md);
if (r > md) upd(l, r, x, 2 * u + 1, md + 1, hg);
}
int qry(int i, int u = 1, int lw = 1, int hg = n) {
if (lw == hg) return tr[u];
int md = (lw + hg) / 2;
if (i <= md) return tr[u] + qry(i, 2 * u, lw, md);
else return tr[u] + qry(i, 2 * u + 1, md + 1, hg);
}
} rm;
arr<set<pii>, N> ord;
void mrg(set<pii> &x, set<pii> &y) {
if (x.size() < y.size()) swap(x, y);
for (pii z : y) x.insert(z);
}
void dfs(int l, int r, int u = 1) {
if (ch[u].empty()) { vl.upd(st[u], +l); return; }
ord[u] = {{wg[u], u}};
for (int v : ch[u]) {
dfs(l, r, v);
mrg(ord[u], ord[v]);
}
while (vl.qry(st[u], fn[u]) > r) {
int v = ord[u].begin()->sec; ord[u].erase(ord[u].begin());
if (rm.qry(st[v])) continue;
int x = vl.qry(st[v], fn[v]) - l, y = vl.qry(st[u], fn[u]) - r;
if (x <= y) {
vl.upd(st[v], -x);
rm.upd(st[v], fn[v], +1);
} else {
vl.upd(st[v], -y);
ord[u].insert({wg[v], v});
}
}
}
int query(sig l, sig r) {
vl.intl(), rm.intl(), ord.fill({});
dfs(l, r);
int ans = vl.cnt();
return ans;
}
