#include"tree.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2e5+5;
int n,m,V,cnt;
vector<int>G[N];
int f[N],a[N],b[N];
LL ans[N],K[N],B[N];
__gnu_pbds::priority_queue<pair<int,int>>T[N];
inline void solve(int u){
    int r=0;
    if(G[u].empty())B[1]+=a[u];
    else if(G[u].size()>1)r+=G[u].size()-1,B[1]+=1ll*a[u]*r,m+=G[u].size()-1;
    for(auto v:G[u]){
        solve(v);
        int z=0;
        while(!T[v].empty()&&T[v].top().first>a[u]){
            const auto [w,y]=T[v].top();T[v].pop();
            if(y>1)
                K[z+2]+=a[u]-w,
                B[z+2]-=1ll*(a[u]-w)*(z+1),
                K[z+y+1]-=a[u]-w,
                B[z+y+1]+=1ll*(a[u]-w)*(z+1);
            B[z+y+1]+=1ll*(a[u]-w)*y,z+=y;
        }
        r+=z;
        T[u].join(T[v]);
    }
    if(r)T[u].push(make_pair(a[u],r));
}
void init(vector<int>P,vector<int>W){
    n=P.size(),m=1;
	for(int i=1;i<=n;++i)
		f[i]=P[i-1]+1,a[i]=W[i-1],
		G[f[i]].emplace_back(i);
	solve(0);
	for(int i=1;i<=m;++i)K[i]+=K[i-1],B[i]+=B[i-1],ans[i]=K[i]*i+B[i];
}
LL query(int L,int R){
    const int t=R/L;
    if(t>=m)return ans[m]*L;
    return ans[t]*L+(ans[t+1]-ans[t])*(R%L);
}
/*
 
*/