#include "tree.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 5;
bool chk;
int n;
ll ans , sml;
vector<int> p , w;
vector<int> g[N];
priority_queue<pair<int , int>> st[N];
int in[N] , out[N] , tim;
set<int> stp;
int logg(int n) { return ceil(log2(n + 1)); }
class segtree {
public :
int sz;
ll kur;
vector<ll> t;
segtree (int n) : sz((1 << logg(n))) , kur(0) , t(vector<ll> (n * 4 , 0)) { }
void update (int v, int l, int r, int j , ll x) {
if(r - l == 1 and l == j) t[v] = x;
else {
int m = (l + r) / 2;
if(j < m) update (v * 2 , l, m, j , x);
else update (v * 2 + 1 , m , r , j , x);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
void gett(int v, int l, int r , int l1 , int r1) {
if(l <= l1 and r >= r1) kur += t[v];
else {
int m = (l1 + r1) / 2;
if(!(l1 >= r || m <= l)) {
gett(v * 2 , l , r , l1 , m);
}
if(!(m >= r || r1 <= l)) {
gett(v * 2 + 1 , l , r , m , r1);
}
}
}
void upd(int p , int x){
update(1 , 0 , sz , p , x);
}
ll get(int l , int r){
kur = 0;
gett(1 , l , r + 1 , 0 , sz);
return kur;
}
};
segtree t(200005);
int l , r;
void dfs(int v){
for(auto to : g[v]){
dfs(to);
}
int u = v;
for(auto to : g[v]){
if(st[to].size() > st[v].size()){
swap(st[v] , st[to]);
}
while(st[to].size()){
st[v].push(st[to].top());
st[to].pop();
}
}
st[v].push({-w[v] , v});
t.upd(in[v] , 0);
if(g[v].size() == 0){
t.upd(in[v] , l);
stp.erase(in[v]);
return ;
}
while(t.get(in[v] , out[v]) > r){
auto u = st[v].top().se;
auto ww = st[v].top().fi;
st[v].pop();
if(stp.find(in[u]) == stp.end()){
continue ;
}
//cout << u << ' ' << ww << '\n';
ll val = min(t.get(in[u] , out[u]) - l , t.get(in[v] , out[v]) - r);
//cout << val << ' ';
ans += 1ll * val * (-ww);
t.upd(in[u] , t.get(in[u] , in[u]) - val);
//cout << t.get(in[u] , out[u]) << ' ';
if(t.get(in[u] , out[u]) == l){
while(stp.lower_bound(in[u]) != stp.end() and (*stp.lower_bound(in[u])) <= out[u]){
stp.erase(stp.lower_bound(in[u]));
}
}
else st[v].push({ww , u});
}
//cout << v << ' ' << ans << '\n';
}
void dffs(int v){
in[v] = (++ tim);
for(auto to : g[v]){
dffs(to);
}
out[v] = tim;
}
void init(std::vector<int> P, std::vector<int> W) {
p = P , w = W;
n = p.size();
chk = 1;
for(int i = 0;i < n; ++ i){
if(w[i] != 1) chk = false;
if(i) g[p[i]].push_back(i);
}
for(int i = 0;i < n; ++ i){
if(g[i].size() == 0){
sml += w[i];
}
}
tim = -1;
dffs(0);
}
long long query(int L, int R) {
ans = 0;
l = L;
r = R;
if(! chk){
ans += 1ll * L * sml;
while(st[0].size()) st[0].pop();
for(int i = 0;i < n; ++ i) stp.insert(i);
dfs(0);
}
else{
//cout << sml << ' ';
ans = 1ll * L * sml + max(0ll , 1ll * L * sml - R);
}
return ans;
}
