#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
vector<int> leaves;
vector<ll> mn;
DSU(int n): p(n), sz(n,1), leaves(n,0), mn(n,0) { iota(p.begin(), p.end(), 0); }
int find(int x){ while(p[x]!=x){ p[x]=p[p[x]]; x=p[x]; } return x; }
int unite(int a,int b){
a=find(a); b=find(b);
if(a==b) return a;
if(sz[a]<sz[b]) swap(a,b);
p[b]=a;
sz[a]+=sz[b];
leaves[a]+=leaves[b];
mn[a]=min(mn[a], mn[b]);
return a;
}
};
static int N;
static vector<int> P;
static vector<ll> W;
static vector<vector<int>> ch;
static vector<char> isLeaf, active;
static ll leafSum;
static int totalLeaves;
static vector<pair<int,ll>> ev;
static vector<ll> prefD, prefKD;
void init(vector<int> _P, vector<int> _W) {
P = _P;
N = (int)P.size();
W.assign(N, 0);
for(int i=0;i<N;i++) W[i] = (ll)_W[i];
ch.assign(N, {});
int root = 0;
for(int i=0;i<N;i++){
if(P[i] == -1) root = i;
else ch[P[i]].push_back(i);
}
isLeaf.assign(N, 0);
leafSum = 0;
totalLeaves = 0;
for(int i=0;i<N;i++){
if(ch[i].empty()){
isLeaf[i] = 1;
leafSum += W[i];
totalLeaves++;
}
}
active.assign(N, 0);
DSU dsu(N);
for(int i=0;i<N;i++){
if(isLeaf[i]){
active[i] = 1;
dsu.leaves[i] = 1;
dsu.mn[i] = 0;
}
}
vector<int> internal;
internal.reserve(N);
for(int i=0;i<N;i++) if(!isLeaf[i]) internal.push_back(i);
sort(internal.begin(), internal.end(), [&](int a,int b){
if(W[a] != W[b]) return W[a] > W[b];
return a < b;
});
ev.clear();
ev.reserve(2LL*N);
auto add_ev = [&](int k, ll d){
if(k <= 0) return;
if(d == 0) return;
ev.push_back({k, d});
};
for(int v: internal){
ll wv = W[v];
active[v] = 1;
dsu.leaves[v] = 0;
dsu.mn[v] = wv;
int r = dsu.find(v);
add_ev(dsu.leaves[r], -dsu.mn[r]);
vector<int> roots;
roots.reserve(ch[v].size() + 1);
if(P[v] != -1 && active[P[v]]) roots.push_back(dsu.find(P[v]));
for(int u: ch[v]) if(active[u]) roots.push_back(dsu.find(u));
sort(roots.begin(), roots.end());
roots.erase(unique(roots.begin(), roots.end()), roots.end());
for(int rr: roots){
rr = dsu.find(rr);
r = dsu.find(r);
if(rr == r) continue;
add_ev(dsu.leaves[rr], -dsu.mn[rr]);
r = dsu.unite(r, rr);
}
r = dsu.find(v);
dsu.mn[r] = wv;
add_ev(dsu.leaves[r], +dsu.mn[r]);
}
sort(ev.begin(), ev.end(), [&](auto &a, auto &b){
if(a.first != b.first) return a.first < b.first;
return a.second < b.second;
});
int m = (int)ev.size();
prefD.assign(m+1, 0);
prefKD.assign(m+1, 0);
for(int i=0;i<m;i++){
prefD[i+1] = prefD[i] + ev[i].second;
prefKD[i+1] = prefKD[i] + (ll)ev[i].first * ev[i].second;
}
}
long long query(int L, int R) {
ll LL = (ll)L, RR = (ll)R;
ll T = (RR + LL - 1) / LL;
if(T <= 1) T = 1;
if(T > totalLeaves + 1) return leafSum * LL;
int m = (int)ev.size();
int idx = lower_bound(ev.begin(), ev.end(), make_pair((int)T, (ll)-4e18),
[&](const pair<int,ll>& a, const pair<int,ll>& b){
if(a.first != b.first) return a.first < b.first;
return a.second < b.second;
}) - ev.begin();
ll sufD = prefD[m] - prefD[idx];
ll sufKD = prefKD[m] - prefKD[idx];
return leafSum * LL + sufKD * LL - sufD * RR;
}
