#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll N; const ll Nm = 2e5+5;
map<ll,ll> snum[Nm];
ll madd[Nm]; //which one does this refer to? (memory address)
ll lans; //coefficient on l for ans
vector<ll> pupd; //inverse prefix sum for the updates
vector<ll> upd; //actual computed updates (subtract from ans)
vector<ll> nhull; //number hull from snum[madd[0]]
void init(vector<int> P, vector<int> W) {
N = P.size();
pupd = vector<ll>(N+1,0);
lans = 0;
vector<ll> fadj[N];
for (ll x=0;x<N;x++) {
snum[x].clear();
madd[x]=x;
}
for (ll i=1;i<N;i++) {
fadj[P[i]].push_back(i);
}
for (ll x=(N-1);x>=0;x--) {
if (fadj[x].size()==0) {
lans += W[x];
} else {
ll F = fadj[x].size();
lans += (F-1)*W[x];
ll zc = -1;
ll msz = -1;
for (ll y: fadj[x]) {
ll z = madd[y];
vector<pii> fupd;
ll flen = 0; //final length (#) of all updates
ll diffr = 0; //SUM of all updates (if can apply all)
while (!snum[z].empty()) {
pii p0 = *(--snum[z].end());
if (p0.first<=W[x]) {
break;
}
snum[z].erase((--snum[z].end()));
fupd.push_back({p0.first-W[x],p0.second});
pupd[flen]+=(p0.first-W[x]);
flen += p0.second;
diffr += p0.second*(p0.first-W[x]);
pupd[flen]-=(p0.first-W[x]);
}
if (flen != 0) {
if (snum[z].find(W[x])==snum[z].end()) {
snum[z][W[x]]=0;
}
snum[z][W[x]]+=flen;
}
//cout << "snum[z].size()="<<snum[z].size()<<"\n";
if ((ll)(snum[z].size())>=(ll)msz) {
//cout << "f1\n";
msz = snum[z].size();
zc = z;
}
}
if (zc==-1) {
//cout << "af\n"; exit(0);
}
assert(zc!=-1);
madd[x]=zc;
for (ll y: fadj[x]) {
ll z = madd[y];
if (z!=zc) {
for (pii p0: snum[z]) {
if (snum[zc].find(p0.first)==snum[zc].end()) {
snum[zc][p0.first]=0;
}
snum[zc][p0.first]+=p0.second;
}
snum[z].clear();
}
}
if (snum[zc].find(W[x])==snum[zc].end()) {
snum[zc][W[x]]=0;
}
snum[zc][W[x]]+=(F-1);
}
}
upd = vector<ll>(N+1,0);
ll vupd = 0;
ll tupd = 0;
upd[0]=0;
for (ll x=0;x<N;x++) {
vupd += pupd[x];
tupd += vupd;
upd[x+1] = tupd;
}
nhull = vector<ll>(N+1,0);
ll xhull = 0;
ll thull = 0;
nhull[0]=0;
while (!snum[madd[0]].empty()) {
auto A0 = (--snum[madd[0]].end());
pii p0 = *A0;
//cout << "p0 term: "<<p0.first<<","<<p0.second<<"\n";
snum[madd[0]].erase(A0);
ll m = p0.first; ll delx = p0.second;
for (ll x=(xhull+1);x<=(xhull+delx);x++) {
thull += m;
nhull[x]=thull;
}
xhull += delx;
}
// cout << "nhull[0]="<<nhull[0]<<"\n";
// cout << "nhull[1]="<<nhull[1]<<"\n";
}
ll query(int L, int R) {
//between val[R/L] and val[R/L+1]
ll a = (R-L)/L; ll b = (R-L)/L+1;
ll ka = L*(1+R/L)-R;
ll kb = R-L*(R/L);
a = min(a,N); b=min(b,N);
ll ans = L*lans;
ans -= ka*(upd[a]+nhull[a]);
ans -= kb*(upd[b]+nhull[b]);
return ans;
}
