#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
#define X first
#define Y second
#define pii pair<ll, ll>
#define pb push_back
const int N = 2e5 + 4;
// const ll INF = 1ll << 60;
ll n;
vector<ll> p, w;
vector<ll> adj[N];
ll sz[N], imp[N];
void prep(int v) {
sz[v] = 1;
imp[v] = -1;
for (int u : adj[v]) {
prep(u);
sz[v] += sz[u];
if (imp[v] == -1 || sz[imp[v]] < sz[u]) imp[v] = u;
}
}
void init(std::vector<int> P, std::vector<int> W) {
n = P.size();
p.resize(n); for (int i=0; i<n; i++) p[i] = P[i];
w.resize(n); for (int i=0; i<n; i++) w[i] = W[i];
for (int i=1; i<n; i++) adj[p[i]].pb(i);
prep(0);
}
ll last = 0;
ll len = 0;
multiset<pii> ret;
void dfs(int v, ll l, ll r) {
if (adj[v].empty()) {
ret.insert({w[v], r-l});
last = r * w[v];
len = r-l;
return;
}
multiset<pii> slope;
ll cur_last = 0;
ll cur_len = 0;
last = len = 0;
ret.clear();
dfs(imp[v], l, r);
swap(slope, ret);
cur_last += last;
cur_len += len;
for (int u : adj[v]) if (u != imp[v]) {
last = len = 0;
ret.clear();
dfs(u, l, r);
for (auto t : ret) slope.insert(t);
cur_last += last;
cur_len += len;
}
last = cur_last;
len = cur_len;
{
ll k = adj[v].size();
ll c = l*k - l;
while (!slope.empty() && slope.begin()->X < -w[v]) {
c += slope.begin()->Y;
len -= slope.begin()->Y;
slope.extract(*slope.begin());
}
// if (slope.empty()) last += -w[v] * c;
slope.insert({-w[v], c});
len += c;
c = N;
last += w[v]*c;
slope.insert({w[v], c});
len += c;
}
ll del = len - (r-l);
assert(0<=del);
while (del != 0) {
auto [x, c] = *slope.rbegin();
slope.extract(*slope.rbegin());
ll t = min(del, c);
last -= t*x;
len -= t;
del -= t;
c -= t;
if (0<c) slope.insert({x, c});
}
// cout << endl;
// cout << "v = " << v << endl;
// cout << "last = " << last << endl;
// cout << "w[" << v << "] = " << w[v] << endl;
// for (auto [x, c] : slope) {
// while (c--) cout << x << ' ';
// }
// cout << endl;
swap(ret, slope);
}
long long query(int L, int R) {
last = len = 0;
ret.clear();
dfs(0, L, R);
ll ans = last;
// cout << "last = " << last << endl;
for (auto [x, c] : ret) {
if (0<x) ans -= x*c;
}
return ans;
}
