#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],nd;
long long ccf[200010],cf[200010],f[200010];
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 g:nd)
	{
		int u=get_fa(g);
		if(u==1) ccf[siz[1]]-=w[g];
		siz[u]--;
		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];
		}
		if(u==1) ccf[siz[1]]+=w[g];
	}
	
	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+2]*L+cf[k+1]*(L-R%L);
}