#include "tree.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define pb push_back
#define F first
#define pii pair<ll,ll>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const ll maxn = 1e5 + 100 , inf = 1e18 , mod = 998244353;
int n;
std::vector<int> p, w;
int h[maxn] , sz[maxn] ;
vector <int >G[maxn] ;
void bui(int v){
sz[v] = 1;
for(int u : G[v]){
bui(u);
sz[v] += sz[u] ;
}
}
int st[maxn] , en[maxn] , id[maxn] , cnt = 0 ;
ll l , r, ans =0 ;
vector <int> tp ;
void bui2(int v){
vector <pii> vec;
id[v] = cnt ;
tp.pb(v) ;
st[v] = cnt ;
cnt++ ;
for(int u : G[v]){
vec.pb({sz[u] , u});
}
sort(all(vec));
reverse(all(vec));
rep(i , 0 ,sz(vec)-1){
int u = vec[i].S ;
if(i ==0 ){
h[u] = h[v] ;
bui2(u);
}else{
h[u] = u;
bui2(u);
}
}
en[v] = cnt-1 ;
}
struct node{
ll mn , sm ,id ;
node(){
mn = sm = id =0 ;
}
};node seg[4*maxn] ;
node operator+(node a , node b){
node r ;
r.mn = min(a.mn , b.mn) ; ;r.id = a.id;
if(r.mn == b.mn)r.id = b.id ;
r.sm =0 ;
return r ;
}
void buiseg(int p = 1, int l = 0 , int r = n-1){
int mid = (l+r)/2 ,pl=p<<1,pr=p<<1|1;
if(l == r){
seg[p].mn = w[tp[l]];
seg[p].id = l ;
seg[p].sm =0 ;
return ;
}
buiseg(pl,l,mid);
buiseg(pr ,mid+1,r);
seg[p] = seg[pl] + seg[pr];
}
void shi(int p){
int pl= p<<1 , pr =p<<1|1 ;
seg[pl].sm+= seg[p].sm ;
seg[pr].sm+= seg[p].sm ;
seg[p].sm =0 ;
}
void upd(int le , int ri , int w , int p =1 , int l =0 , int r = n-1){
int mid = (l+r)/2 , pl=p<<1, pr=p<<1|1;
if(le > r || l > ri)return;
if(le <= l && r <= ri){
seg[p].sm += w ;
return;
}
shi(p);
upd(le,ri,w,pl,l,mid);
upd(le,ri,w,pr,mid+1,r);
seg[p] = seg[pl] + seg[pr];
}
node que(int le ,int ri , int p =1 ,int l = 0,int r =n-1){
int mid = (l+r)/2 , pl=p<<1, pr=p<<1|1;
if(le <= l && r <=ri)return seg[p];
shi(p) ;
if(ri <= mid)return que(le,ri,pl,l,mid);
if(le > mid)return que(le,ri,pr,mid+1,r);
return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r);
}
void msir(int v, int w){
if(h[v]==0){
upd(0 , id[v] , w) ;
return ;
}
upd(id[h[v]] , id[v] , w) ;
v = p[h[v]] ;
msir(v, w) ;
}
void init(std::vector<int> P, std::vector<int> W) {
p = P;
w = W;
n = (int)p.size();
rep(i ,1, n-1){
G[p[i]].pb(i) ;
}
bui(0);bui2(0);
}
void rem(int x, int p =1 , int l =0 , int r = n-1){
int mid = (l+r)/2 , pl=p<<1, pr=p<<1|1;
if(x > r || l > x)return;
if(l == r){
seg[p].mn = inf ;
return;
}
shi(p);
rem(x,pl,l,mid);
rem(x,pr,mid+1,r);
seg[p] = seg[pl] + seg[pr];
}
int f(int v){return que(v,v).sm ;}
void dfs(int v){
if(sz(G[v]) == 0){
msir(v, l) ;
ans += 1ll * l * w[v] ;
return;
}
for(int u : G[v]){
dfs(u);
}
while(f(v) > r){
node a =que(st[v] , en[v]) ;
int u = tp[a.id] ;
if(f(u) == l){
rem(a.id);
continue ;
}
ll x = min(f(v)-r ,f(u) - l) ;
ans += x * w[u] ;
msir(u, -x) ;
}
}
long long query(int L2, int R2) {
buiseg();
ans = 0;
l= L2 ;
r= R2 ;
dfs(0 );
return ans ;
}
