#include "tree.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
typedef long long ll;
namespace{
const ll mxN=2e5+5;
const ll inf=1e18;
struct segtreeadd{
vll tree;
ll siz;
void init(ll sz){
siz=sz+1;
tree=vll(siz, 0);
}
void update(ll idx, ll val){
idx++;
for(;idx<siz;idx+=(idx&(-idx))){
tree[idx]+=val;
}
}
ll getpre(ll idx){
idx++;
ll re=0;
for(;idx>0;idx-=(idx&(-idx))){
re+=tree[idx];
}
return re;
}
ll getsum(ll qlow, ll qhigh){
return getpre(qhigh)-getpre(qlow-1);
}
};
struct segtreemin{
vector<pll> tree;
ll treelen;
void init(ll sz){
treelen=sz+1;
while(__builtin_popcount(treelen)!=1) treelen++;
tree=vector<pll>(2*treelen, {inf, inf});
}
void update(ll idx, pll val){
ll tar=idx+treelen;
tree[tar]=val;
tar/=2;
while(tar>0){
tree[tar]=min(tree[2*tar], tree[2*tar+1]);
tar/=2;
}
}
pll getmin1(ll idx, ll low, ll high, ll qlow, ll qhigh){
if(low>=qlow && high<=qhigh){
return tree[idx];
}
if(low>qhigh || high<qlow){
return {inf, inf};
}
ll mid=(low+high)/2;
return min(getmin1(2*idx, low, mid, qlow, qhigh),
getmin1(2*idx+1, mid+1, high, qlow, qhigh));
}
pll getmin(ll qlow, ll qhigh){
return getmin1(1, 0, treelen-1, qlow, qhigh);
}
};
segtreeadd seg1;
segtreemin seg2;
ll n, l, r;
ll p[mxN];
ll w[mxN];
vll adj[mxN];
ll in[mxN], out[mxN];
ll timer;
ll ans;
void dfs(ll cur){
in[cur]=timer;
out[cur]=timer;
timer++;
for(auto &chd:adj[cur]){
dfs(chd);
out[cur]=out[chd];
}
}
void chainupd(ll t, ll b, ll val){
seg1.update(in[b], val);
if(p[t]!=-1){
seg1.update(in[p[t]], -val);
}
}
void f(ll cur){
pll tep=seg2.getmin(in[cur], out[cur]);
if(tep.F==inf) return;
ll tar=tep.S;
// cout<<seg1.getsum(in[cur], out[cur])<<'\n';
ll mx=max(seg1.getsum(in[cur], out[cur])-r, 0LL);
ll lef=0;
ll minu=seg1.getsum(in[tar], out[tar]);
for(auto &chd:adj[tar]){
ll val=min(seg1.getsum(in[chd], out[chd]), r);
lef+=val;
minu-=val;
}
lef-=l;
lef=min(lef, mx-minu);
ans+=w[tar]*lef;
// cout<<"node: "<<tar<<' '<<lef<<' '<<mx<<'\n';
chainupd(cur, tar, -lef-minu);
// cout<<"updating "<<cur<<' '<<tar<<' '<<-lef<<'\n';
seg2.update(in[tar], {inf, inf});
for(auto &chd:adj[tar]){
f(chd);
}
f(cur);
}
}
void init(vector<int> P, vector<int> W) {
n=P.size();
for(ll i=0;i<n;i++){
p[i]=P[i];
w[i]=W[i];
if(i>0){
adj[p[i]].pb(i);
}
}
timer=0;
dfs(0);
}
long long query(int L, int R) {
ans=0;
l=L;
r=R;
seg1.init(n);
seg2.init(n);
for(ll i=0;i<n;i++){
if(in[i]==out[i]){
seg1.update(in[i], l);
seg2.update(in[i], {inf, inf});
ans+=l*w[i];
}
else{
seg2.update(in[i], {w[i], i});
}
}
f(0);
return ans;
}
