#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define X first
#define Y second
#define pii pair<int, int>
const int N = 200200;
int n;
std::vector<int> w, p;
vector<int> adj[N];
int sz[N];
int 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;
}
}
priority_queue<pii> pq;
ll res;
ll sum[N];
void add(int v, int l, int r) {
if (sum[v]==l) return;
pq.push({-w[v], v});
for (int u : adj[v]) add(u, l, r);
}
void dfs(int v, ll l, ll r) {
sum[v]=0;
if (adj[v].empty()) {
sum[v] = l;
res += w[v] * l;
pq.push({-w[v], v});
return;
}
for (int u : adj[v]) if (u != imp[v]) {
dfs(u, l, r);
sum[v] += sum[u];
while (!pq.empty()) pq.pop();
}
{
dfs(imp[v], l, r);
sum[v] += sum[imp[v]];
}
for (int u : adj[v]) if (u != imp[v]) add(u, l, r);
pq.push({-w[v], v});
if (sum[v] <= r) return;
while (sum[v] != r) {
int x = pq.top().Y;
pq.pop();
int save_x = x;
ll mn = sum[v] - r;
while (x != v) {
mn = min(mn, sum[x] - l);
x = p[x];
}
x = save_x;
res += mn * w[x];
while (x != v) {
sum[x] -= mn;
x = p[x];
}
assert(v==x);
sum[x] -= mn;
x = save_x;
// if (sum[v]==r) pq.push({-w[x], x});
}
}
void init(std::vector<int> P, std::vector<int> W) {
p = P;
w = W;
n = W.size();
for (int i=1; i<n; i++) adj[P[i]].pb(i);
prep(0);
}
long long query(int L, int R) {
res = 0;
while (!pq.empty()) pq.pop();
dfs(0, L, R);
return res;
}
