#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define pb push_back
#define sz(x) (int)(x).size()
#define rsz resize
#define ass assign
#define F(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define each(a,x) for(auto a:x)
#define FOR(i,a) for(int i=0;i<(a);i++)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define eb emplace_back
#define ft front()
#define V vector
#include "tree.h"
struct node{
ll fl,slope;
V<pll> jumps;//pos,delta
};
V<int> par,weis;
V<V<int>> child;
int n;
void init(V<int> p,V<int> w){
n=sz(p);
par=p;
weis=w;
child.ass(n,V<int>());
F(i,1,n)child[p[i]].pb(i);
}
ll query(int l,int r){
ll delta=r-l;
V<node> dp(n);
ROF(i,0,n){
int k=sz(child[i]);
if(!k)dp[i]={(ll)weis[i]*l,(ll)weis[i],{}};
else{
ll sumfl=0,sumslope=0;
V<pll> merged;
each(ch,child[i]){
sumfl+=dp[ch].fl;
sumslope+=dp[ch].slope;
each(j,dp[ch].jumps){
ll npos=j.fi+(ll)(k-1)*l;
if(npos<=delta)merged.pb({npos,j.se});
}
}
sort(merged.begin(),merged.end());
dp[i].fl=(ll)(k-1)*l*weis[i]+sumfl;
dp[i].slope=-weis[i];
ll curslope=sumslope,stg=(ll)(k-1)*l;
if(stg<=delta){
ll jump_amt=max(0LL,min((ll)weis[i],curslope)+weis[i]);
if(jump_amt>0)dp[i].jumps.pb({stg,jump_amt});
}
ll seff=(stg<=0)?max(-(ll)weis[i],min((ll)weis[i],sumslope)):-weis[i];
dp[i].slope=seff;
each(j,merged){
if(j.fi<stg)continue;
//ll oldg=curslope;
curslope+=j.se;
ll nseff=max(-(ll)weis[i],min((ll)weis[i],curslope));
if(nseff>seff){
dp[i].jumps.pb({j.fi,nseff-seff});
seff=nseff;
}
}
}
}
ll mncost=dp[0].fl,curf=dp[0].fl,curs=dp[0].slope;
ll lastx=0;
each(j,dp[0].jumps){
curf+=curs*(j.fi-lastx);
mncost=min(mncost,curf);
curs+=j.se;
lastx=j.fi;
}
curf+=curs*(delta-lastx);
mncost=min(mncost,curf);
return mncost;
}
