#include "tree.h"
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#define N 800000
using namespace std;
struct reads
{
	int num;
	long long A,B;
	bool operator < (const reads &t)const
	{
		return num>t.num;	
	}
};
reads tong[N+1];
int n,L,R,ds,scnt,length,lg[N+1],rt[N+1],p[N+1],delta[N+1],sz[N+1],cnt[N+1];
bool used[N+1];
vector<int>E[N+1];
bool cmp(int x,int y)
{
	return delta[x]>delta[y];
}
void adder(int x,int d)
{
	tong[++length]=(reads){x,1ll*d*x,-d};
	return;
}
int find(int x)
{
	if (rt[x]==x) return x;
	return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
	adder(cnt[x]-(sz[x]-1),-ds),adder(cnt[y]-(sz[y]-1),-ds),sz[y]+=sz[x],cnt[y]+=cnt[x],adder(cnt[y]-(sz[y]-1),ds),rt[x]=y;
	return;
}
void init(std::vector<int> P, std::vector<int> W)
{
	int x;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	n=P.size();
	for (int i=1;i<n;++i) E[P[i]].push_back(i);
	for (int i=0;i<n;++i) delta[i]=W[i],p[i]=rt[i]=i,sz[i]=1,cnt[i]=E[i].size();
	sort(p,p+n,cmp);
	for (int i=0;i<n;++i)
	{
		x=p[i];
		if (!E[x].empty())
		{
			ds=delta[x],used[x]=1,adder(cnt[x]-(sz[x]-1),ds);
			for (int j=0;j<E[x].size();++j)
				if (used[E[x][j]])
					unionn(E[x][j],x);
			if (x&&used[P[x]]) unionn(x,find(P[x]));
		}
		else scnt++;
	}
	sort(tong+1,tong+length+1);
	for (int i=1;i<=length;++i) tong[i].A+=tong[i-1].A,tong[i].B+=tong[i-1].B;
	return;
}
long long query(int sl,int sr)
{
	int ps=0;
	for (int i=lg[length];i>=0;--i)
		if (ps+(1<<i)<=length&&tong[ps+(1<<i)].num>sr/sl)
			ps+=(1<<i);
	return (tong[ps].A+scnt)*sl+tong[ps].B*sr;
}