#include<bits/stdc++.h>
using namespace std;
#define INFint 1000000000
vector<vector<int>> Children;
vector<int> RangeSize;
vector<pair<int,int>> WeightsSegTree;
vector<long long> ValArray;
vector<int> XtoIndx;
pair<int,int> setWeightTree(int pos,int l, int r,int n,pair<int,int> value){
if(pos>r){
return WeightsSegTree[n];
}
if(pos<l){
return WeightsSegTree[n];
}
if(pos==l && l==r){
WeightsSegTree[n]=value;
return value;
}
pair<int,int> a=setWeightTree(pos,l,(l+r)/2,n*2,value);
pair<int,int> b=setWeightTree(pos,(l+r)/2+1,r,n*2+1,value);
if(b<a){
a=b;
}
WeightsSegTree[n]=a;
return a;
}
int dfs(int x,std::vector<int>& W,int indx){
int children=1;
setWeightTree(indx,0,W.size(),1,{W[x],x});
XtoIndx[x]=indx;
for(int i=0;i<Children[x].size();i++){
children+=dfs(Children[x][i],W,indx+children);
}
RangeSize[x]=children;
return children;
}
void init(std::vector<int> P, std::vector<int> W){
Children=vector<vector<int>>(P.size());
RangeSize=vector<int>(P.size());
XtoIndx=vector<int>(P.size());
WeightsSegTree=vector<pair<int,int>>(6*P.size());
for(int i=1;i<P.size();i++){
Children[P[i]].push_back(i);
}
dfs(0,W,0);
}
long long SetValue(int pos,int l, int r,int n,int value){
if(pos>r){
return ValArray[n];
}
if(pos<l){
return ValArray[n];
}
if(pos==l && l==r){
ValArray[n]=value;
return value;
}
long long val=SetValue(pos,l,(l+r)/2,n*2,value)+SetValue(pos,(l+r)/2+1,r,n*2+1,value);
ValArray[n]=val;
return val;
}
long long GetValueRange(int x,int y,int l, int r,int n){
if(x>r){
return 0;
}
if(y<l){
return ValArray[n];
}
if(x<=l && r<=y){
return ValArray[n];
}
long long val=GetValueRange(x,y,l,(l+r)/2,n*2)+GetValueRange(x,y,(l+r)/2+1,r,n*2+1);
return val;
}
pair<int,int> GetBestRange(int x,int y,int l, int r,int n){
if(x>r){
return {INFint,0};
}
if(y<l){
return {INFint,0};
}
if(x<=l && r<=y){
return WeightsSegTree[n];
}
pair<int,int> val=min(GetBestRange(x,y,l,(l+r)/2,n*2),GetBestRange(x,y,(l+r)/2+1,r,n*2+1));
return val;
}
long long getValue(int x){
int pos=XtoIndx[x];
return GetValueRange(pos,pos+RangeSize[x]-1,0,RangeSize.size(),1);
}
a
pair<int,int> getBest(int x){
int pos=XtoIndx[x];
return GetBestRange(pos,pos+RangeSize[x]-1,0,RangeSize.size(),1);
}
long long dfsGetVal(int x,int L,int R){
long long baseCost=0;
if(Children[x].size()==0){
int cost=L*getBest(x).first;
setWeightTree(XtoIndx[x],0,XtoIndx.size(),1,{INFint,0});
SetValue(XtoIndx[x],0,XtoIndx.size(),1,L);
return cost;
}
for(int i=0;i<Children[x].size();i++){
baseCost+=dfsGetVal(Children[x][i],L,R);
}
int val=getValue(x);
while(val>R){
pair<int,int> P=getBest(x);
long long sub=getValue(P.second);
if(val-sub+L<R){
SetValue(XtoIndx[P.second],0,XtoIndx.size(),1,sub-val+R);
baseCost+=P.first*(val-R);
val=R;
}
else{
SetValue(XtoIndx[P.second],0,XtoIndx.size(),1,L);
setWeightTree(XtoIndx[P.second],0,XtoIndx.size(),1,{INFint,0});
val-=sub-L;
baseCost+=P.first*(sub);
}
}
return baseCost;
}
long long query(int L, int R){
ValArray=vector<long long>(RangeSize.size()*4);
vector<pair<int,int>> WtC=WeightsSegTree;
return dfsGetVal(0,L,R);
}
