#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,c[N];
ll ans[N];int sz[N];
void init(vi P,vi W){
	n=P.size();w=W;dlt=0;
	vi key(n,1);
	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];
		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));
	int las=0;
	for(auto [v,x]:seq){
		for(int i=0;i<n;++i)
			if(key[i]){
				dlt+=v-las;
				for(int t:vec[i]) ans[sz[t]]+=v-las;
			}
		ans[sz[0]]+=v-las;

		key[x]=1;
		for(int i=0;i<n;++i) sz[i]=0;
		for(int i=n-1;~i;--i){
			if(key[i]) sz[i]=1;
			if(i) sz[P[i]]+=sz[i];
		}
		las=v;
	}
}
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;
}