#include <bits/stdc++.h>
#include "tree.h"
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;
int n;
vector<ll> par, w;
vvi G;
void init(vi P, vi W) {
n = W.size(); G.resize(n);
for (auto &el : P) par.push_back(el);
for (auto &el : W) w.push_back(el);
for (int i = 1; i < n; i++) G[par[i]].push_back(i);
}
struct state {ll cost, sum; multiset<pi> usef;};
state dfs(int u, int L, int R) {
if (G[u].empty()) {
multiset<pi> us; us.insert({w[u], L});
state myst{L * w[u], L, us};
return myst;
}
multiset<pi> nws;
ll tc = 0, sum = 0;
for (auto v : G[u]) {
auto r = dfs(v, L, R);
tc += r.cost; sum += r.sum;
if (r.usef.size() > nws.size()) swap(nws, r.usef);
for (auto &el : r.usef) nws.insert(el);
}
ll coff = min(0LL, R-sum); sum += coff; tc += abs(coff) * w[u];
while (!nws.empty() && nws.begin()->first < w[u]) {
auto x = *nws.begin(); nws.erase(nws.find(x));
ll diff = min(sum-L, R-x.second);
tc -= w[u] * diff; tc += x.first * diff;
coff += diff;
}
nws.insert({w[u], sum});
return state{tc, sum, nws};
}
ll query(int L, int R) {
return dfs(0, L, R).cost;
}
