#include <bits/stdc++.h>
#include "tree.h"
using namespace std;

int fa[200010];
int get_fa(int a){return a==fa[a]?a:fa[a]=get_fa(fa[a]);}

int n,w[200010],siz[200010];
vector<int> son[200010];
long long ccf[200010],cf[200010],f[200010];
vector<int> nd;
void init(std::vector<int> P, std::vector<int> W)
{
	n=W.size();
	for(int i=2;i<=n;i++) son[P[i-1]+1].push_back(i);
	for(int i=1;i<=n;i++) w[i]=W[i-1];

	for(int i=1;i<=n;i++)
	{
		if(son[i].empty()) f[n+2]+=w[i];
		else nd.push_back(i);
		fa[i]=i,siz[i]=1;
	}
	sort(nd.begin(),nd.end(),[&](int a,int b){return w[a]>w[b];});
	for(int x:nd)
	{
		int y=get_fa(x),u=P[y-1]+1,tk=-1;
		for(int z:son[x]) tk+=siz[z],fa[z]=x;
		ccf[siz[y]+tk]+=w[x]-w[u],ccf[siz[y]]-=w[x]-w[u];
		siz[y]+=tk;
	}
	
	for(int i=n+1;i;i--) cf[i]=cf[i+1]+ccf[i];
	for(int i=n+1;i;i--) f[i]=f[i+1]+cf[i];
}

long long query(int L, int R)
{
	int k=min(R/L,n);
	return f[k+1]*L-cf[k+1]*R%L;
}