#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 60000;
struct LazySeg {
int n;
vector<ll> tree, lz;
LazySeg(int n) {
this->n = n;
tree = vector<ll>(4 * n);
lz = vector<ll>(4 * n);
}
void init() {
tree = vector<ll>(4 * n);
lz = vector<ll>(4 * n);
}
void push(int i) {
tree[i * 2] += lz[i];
tree[i * 2 + 1] += lz[i];
lz[i * 2] += lz[i];
lz[i * 2 + 1] += lz[i];
lz[i] = 0;
}
void update(int i, int l, int r, int ql, int qr, ll delta) {
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) {
tree[i] += delta;
lz[i] += delta;
return;
}
push(i);
int m = (l + r) / 2;
if (ql <= m) update(i * 2, l, m, ql, qr, delta);
if (qr > m) update(i * 2 + 1, m + 1, r, ql, qr, delta);
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
void update(int ql, int qr, ll delta) {
update(1, 1, n, ql, qr, delta);
}
ll query(int i, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return 0;
if (ql <= l && r <= qr) return tree[i];
push(i);
int m = (l + r) / 2;
return query(i * 2, l, m, ql, qr) + query(i * 2 + 1, m + 1, r, ql, qr);
}
ll query(int ql, int qr) {
return query(1, 1, n, ql, qr);
}
} sums(2 * MAXN), del(2 * MAXN);
int N;
vector<int> W;
vector<int> adj[MAXN];
vector<int> P;
int tin[MAXN], tout[MAXN];
void init(vector<int> _P, vector<int> _W) {
P = _P;
P[0] = -1;
W = _W;
N = (int)P.size();
for (int i = 1; i < N; i++) {
adj[P[i]].push_back(i);
}
int t = 0;
auto dfs = [&](auto& dfs, int v) -> void {
tin[v] = ++t;
for (auto& u : adj[v]) {
dfs(dfs, u);
}
tout[v] = t;
};
dfs(dfs, 0);
}
long long query(int L, int R) {
sums.init();
del.init();
cerr << "Query " << L << " " << R << "\n";
ll res = 0;
vector<set<pair<int, int>>> mn(N);
auto dfs = [&](auto& dfs, int v) -> void {
// cerr << "Now at v = " << v << "\n";
if ((int)adj[v].size() == 0) {
res += L * W[v];
sums.update(tin[v], tin[v], +L);
// cerr << "v = " << v << ", tin = " << tin[v] << " , tout = " << tout[v] << "\n";
// cerr << "Sum at v = " << v << " is = " << sums.query(tin[v], tout[v]) << "\n";
return;
}
mn[v].insert({W[v], v});
for (auto& u : adj[v]) {
dfs(dfs, u);
if (mn[u].size() > mn[v].size()) swap(mn[u], mn[v]);
for (auto& val : mn[u]) mn[v].insert(val);
mn[u].clear();
}
ll current_sum = sums.query(tin[v], tout[v]);
// cerr << "v = " << v << ", tin = " << tin[v] << " , tout = " << tout[v] << "\n";
// cerr << "Sum at v = " << v << " is = " << current_sum << "\n";
assert(current_sum >= L);
while (current_sum > R) {
int u = (*begin(mn[v])).second;
int deleted = del.query(tin[u], tin[u]);
if (deleted > 0) {
mn[v].erase(mn[v].begin());
continue;
}
ll need = min(current_sum - R, sums.query(tin[u], tout[u]) - L);
current_sum -= need;
sums.update(tin[u], tin[u], -need);
res += need * W[u];
if (sums.query(tin[u], tout[u]) == L) {
mn[v].erase(begin(mn[v]));
del.update(tin[u], tout[u], +1);
}
}
};
dfs(dfs, 0);
return res;
}
