#include<iostream>
#include<algorithm>
#include<vector>
#include "tree.h"
using namespace std;
const int MAX_N=2e5+5;
long long w[MAX_N];
vector<int>g[MAX_N];
int deg[MAX_N];
vector<pair<long long,long long>>rem[MAX_N];
int n;
long long l,r;
long long ans;
long long sum[MAX_N];
void dfs(int u)
{
for(int v:g[u])
{
dfs(v);
sum[u]+=sum[v];
for(auto [price,howmuch]:rem[v])
{
rem[u].push_back({price,howmuch});
}
}
if(deg[u]==0)
{
sum[u]=l;
ans+=l*w[u];
return;
}
sort(rem[u].rbegin(),rem[u].rend());
long long haveto=sum[u]-r;
while(haveto>0 && rem[u].size())
{
auto [price,howmuch]=rem[u].back();
if(w[u]>price)
{
long long need=min(haveto,howmuch);
haveto-=need;
sum[u]-=need;
ans+=price*need;
if(howmuch==need)
{
rem[u].pop_back();
}
else
{
rem[u].back().second=howmuch-need;
break;
}
}
else
{
ans+=haveto*w[u];
sum[u]-=haveto;
rem[u].clear();
haveto=0;
break;
}
}
if(haveto>0)
{
ans+=haveto*w[u];
sum[u]-=haveto;
}
reverse(rem[u].begin(),rem[u].end());
while(rem[u].size() && rem[u].back().first>=w[u])
{
rem[u].pop_back();
}
long long cursum=sum[u];
for(auto [price,howmuch]:rem[u])
{
cursum-=howmuch;
}
if(cursum>l)rem[u].push_back({w[u],cursum-l});
}
void init(std::vector<int> P, std::vector<int> W)
{
n=P.size();
w[0]=W[0];
for(int i=1;i<n;i++)
{
w[i]=W[i];
deg[P[i]]++;
g[P[i]].push_back(i);
}
}
long long query(int L, int R)
{
l=L;
r=R;
ans=0;
for(int i=0;i<n;i++){rem[i].clear();sum[i]=0;}
dfs(0);
return ans;
}
