#include "tree.h"
#include <algorithm>
#define ALL(vc) (vc).begin(),(vc).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=200003,INF=0x3f3f3f3f;
int n;ll L,R,dlt;
vi vec[N];
ll ans[N];int tr[N],f[N];
ll pre[N],suf[N];
int rt(int x){
	if(f[x]==x) return x;
	return f[x]=rt(f[x]);
}
int dfn[N],sz[N],num;
void dfs(int u){
	sz[u]=1;dfn[u]=++num;
	for(int v:vec[u]) dfs(v),sz[u]+=sz[v];
}
void upd(int x,int v){while(x) tr[x]+=v,x^=(x&-x);}
int qry(int x){
	ll res=0;
	while(x<=n) res+=tr[x],x+=(x&-x);
	return res;
}
int calc(int x){return qry(dfn[x])-qry(dfn[x]+sz[x]);}
void init(vi P,vi W){
	int las=0,cnt=0;num=0;
	n=P.size();dlt=0;
	vi tim(n),tp(n),del(n);
	vector<pii> seq;
	for(int i=1;i<=n;++i) tr[i]=0,ans[i]=0;
	for(int i=1;i<n;++i) vec[P[i]].emplace_back(i);
	dfs(0);
	for(int i=n-1;~i;--i){
		if(vec[i].empty()) upd(dfn[i],1),dlt+=W[i],++cnt;
		else seq.emplace_back(W[i],i);
		f[i]=i;
	}
	sort(ALL(seq),greater<pii>());
	for(auto [v,x]:seq){
		if(x&&del[P[x]]) f[x]=P[x];
		for(int i:vec[x]) if(del[i]) f[i]=x;
		del[x]=1;tp[x]=rt(x);
	}
	reverse(ALL(seq));
	for(auto [v,x]:seq){
		dlt+=(ll)(v-las)*cnt++;las=v;
		for(int i:vec[x]) tim[i]=v;
		int p=tp[x];
		ans[calc(p)]+=v-tim[p];tim[p]=v;
		int sx=calc(x);
		upd(dfn[x],1-sx);
		if(p) upd(dfn[P[p]],sx-1);
	}
	for(int i=0;i<n;++i) ans[calc(i)]+=las-tim[i];
	for(int i=1;i<=n;++i) pre[i]=pre[i-1]+i*ans[i];
	for(int i=n;i;--i) suf[i]=suf[i+1]+ans[i];
}
ll query(int _L,int _R){
	L=_L;R=_R;ll res=dlt*L;
	return res-pre[R/L]*L-suf[R/L]*R;
}