#include "tree.h"
#include <set>
#include <cstdio>
#include <cassert>
#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;
vi vec[N];
vi w;ll dlt;
ll ans[N];int sz[N];
void init(vi P,vi W){
	int las=0,cnt=0;
	n=P.size();w=W;dlt=0;
	vi key(n,1),tim(n);
	vector<pii> seq;
	for(int i=1;i<n;++i){
		key[P[i]]=0;
		vec[P[i]].emplace_back(i);
	}
	for(int i=0;i<n;++i) sz[i]=0;
	for(int i=n-1;~i;--i){
		if(key[i]) sz[i]=1,dlt+=w[i],++cnt;
		else seq.emplace_back(w[i],i);
		if(i) sz[P[i]]+=sz[i];
	}
	for(int i=0;i<=n;++i) ans[i]=0;
	sort(ALL(seq));
	for(auto [v,x]:seq){
		dlt+=(ll)(v-las)*cnt++;
		las=v;
		key[x]=1;
		for(int i=x,d=sz[x]-1;;i=P[i]){
			sz[i]-=d;
			if(!i||key[P[i]]){
				ans[sz[i]+d]+=v-tim[i];
				tim[i]=v;
				break;
			}
		}
	}
	for(int i=0;i<n;++i) if(!vec[i].empty()) ans[sz[i]]+=las-tim[i];
}
ll query(int _L,int _R){
	L=_L;R=_R;ll res=dlt*L;
	for(int i=1;i<=n;++i) res-=min(L*i,R)*ans[i];
	return res;
}