#include "tree.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vi vector<int>
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl
#define vout(v) cout<<#v<<": "; for(auto u : v)cout<<u<<' '; cout<<endl
using namespace std;
const int mxn = 2e5 + 5;
int n, par[mxn], w[mxn], dp[mxn], L, R, ans; vi adj[mxn];
void merge(multiset<pii> &a, multiset<pii> b){
if(a.size() < b.size())swap(a,b); for(auto u : b)a.insert(u);
}
multiset<pair<int,int>>solve(int node){
multiset<pii>d; int cnt = 0; for(auto u : adj[node]){cnt++; merge(d,solve(u)); dp[node] += dp[u];}
if(cnt==0){dp[node]=L; ans += L; return d;} int fi = dp[node] - L; for(auto u : adj[node])fi -= (dp[u] - L);
while(!d.empty() && (*(--d.end())).F > w[node]){fi += (*(--d.end())).S, d.erase(--d.end());}
d.insert(mp(w[node],fi));
while(dp[node] > R){
auto cur = *d.begin(); if(cur.S <= (dp[node] - R))dp[node] -= cur.S, ans += cur.S * cur.F, d.erase(d.begin()); else{
ans += cur.S * (dp[node] - R); int ne = cur.S - (dp[node] - R); d.erase(d.find(cur)); d.insert(mp(cur.F, ne)); dp[node] = R;
}
} return d;
}
void init(std::vector<signed> P, std::vector<signed> W) {
n = (int)P.size(); f0r(i,n){par[i]=P[i]; if(par[i]!=-1)adj[par[i]].pb(i); w[i]=W[i];}
}
long long query(signed L, signed R) {
::L=L, ::R=R; ans = 0; f0r(i,n)dp[i] = 0; solve(0); return ans;
}
