#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#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];
multiset<pair<long long,long long>>rem[MAX_N];
int n;
long long l,r;
long long ans;
long long sum[MAX_N];
long long sumrem[MAX_N];
void dfs(int u)
{
int mxsz=0;
int which=-1;
for(int v:g[u])
{
dfs(v);
sum[u]+=sum[v];
sumrem[u]+=sumrem[v];
if(rem[v].size()>mxsz)
{
mxsz=rem[v].size();
which=v;
}
}
if(which!=-1)
{
swap(rem[which],rem[u]);
multiset<pair<long long,long long>>().swap(rem[which]);
}
for(int v:g[u])
{
if(v!=which)
{
for(auto [price,howmuch]:rem[v])
{
rem[u].insert({price,howmuch});
}
multiset<pair<long long,long long>>().swap(rem[v]);
}
}
if(deg[u]==0)
{
sum[u]=l;
ans+=l*w[u];
return;
}
long long haveto=sum[u]-r;
while(haveto>0 && rem[u].size())
{
auto [price,howmuch]=(*(rem[u].begin()));
if(w[u]>price)
{
long long need=min(haveto,howmuch);
sumrem[u]-=need;
rem[u].erase(rem[u].find({price,howmuch}));
haveto-=need;
sum[u]-=need;
ans+=price*need;
if(howmuch==need)
{
;
}
else
{
rem[u].insert({price,howmuch-need});
break;
}
}
else
{
ans+=haveto*w[u];
sum[u]-=haveto;
rem[u].clear();
sumrem[u]=0;
haveto=0;
break;
}
}
if(haveto>0)
{
ans+=haveto*w[u];
sum[u]-=haveto;
}
while(rem[u].size() && (*(rem[u].rbegin())).first>=w[u])
{
sumrem[u]-=(*(rem[u].rbegin())).second;
rem[u].erase(rem[u].find((*(rem[u].rbegin()))));
}
long long cursum=sum[u]-sumrem[u];
if(cursum>l)rem[u].insert({w[u],cursum-l});
sumrem[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++){sumrem[i]=0;rem[i].clear();sum[i]=0;}
dfs(0);
return ans;
}
