#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 a[200010],b[200010];
int 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+1]+=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 g:nd)
	{
		int u=get_fa(g);
		ccf[siz[u]]-=w[g];
		for(int v:son[g])
		{
			fa[v]=u,siz[u]+=siz[v];
			ccf[siz[v]]+=w[v]-w[g],ccf[1]-=w[v]-w[g];
		}
		ccf[siz[u]]=w[g];
	}
	for(int i=n;i;i--) cf[i]=cf[i+1]+ccf[i];
	for(int i=n;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+2]*L-cf[k+1]*(R-k*L);
}