#include "tree.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, l, r, subtask_id = 7;
vector<int>p, w;
namespace sub4{
int k;
void init(){
vector<int>deg(n, 0);
for(int i = 1; i < n; i++){
deg[p[i]]++;
}
k = count(deg.begin() + 1, deg.end(), 0);
}
ll solve(){
return ll(l) * k + max(0LL, ll(l) * k - r);
}
}
namespace sub5{
int leave_sum = 0;
vector<int>leave_cnt, cnt, pf;
void init(){
vector<int>deg(n, 0);
for(int i = 1; i < n; i++){
deg[p[i]]++;
}
leave_cnt.assign(n, 0);
for(int i = n - 1; i > -1; i--){
leave_sum += deg[i] == 0 ? w[i] : 0;
leave_cnt[i] += deg[i] == 0 || w[i] == 0;
if(i > 0 && w[p[i]] == 1){
leave_cnt[p[i]] += leave_cnt[i];
}
else if(w[i] == 1){
cnt.push_back(leave_cnt[i]);
}
}
sort(cnt.begin(), cnt.end());
pf.resize(cnt.size() + 1);
pf[0] = 0;
partial_sum(cnt.begin(), cnt.end(), pf.begin() + 1);
}
ll solve(){
int v = upper_bound(cnt.begin(), cnt.end(), r / l) - cnt.begin();
return ll(l) * (leave_sum + pf.back() - pf[v]) - ll(r) * (int(cnt.size()) - v);
}
}
namespace sub12367{
const int lim = 2e5 + 5;
ll f[lim], cf[lim];
void init(){
vector<vector<int>>g(n + 1);
p.insert(p.begin(), 0);
w.insert(w.begin(), 0);
for(int i = 1; i <= n; i++){
g[++p[i]].push_back(i);
}
vector<int>ord, lab(n + 1), siz(n + 1, 1);
memset(cf, f[n + 2] = lab[0] = 0, sizeof(cf));
auto find_set = [&] (int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
};
for(int i = 1; i <= n; i++){
if(g[lab[i] = i].empty()){
f[n + 2] += w[i];
}
else{
ord.push_back(i);
}
}
sort(ord.begin(), ord.end(), [&] (int i, int j){
return w[i] > w[j];
});
for(int& x : ord){
int root = find_set(x), par_root = p[root], cnt = -1;
for(int& y : g[x]){
cnt += siz[y];
lab[y] = root;
}
cf[siz[root] + cnt] += w[x] - w[par_root];
cf[siz[root]] -= w[x] - w[par_root];
siz[root] += cnt;
}
for(int i = n + 1; i > 0; i--){
f[i] = f[i + 1] + (cf[i] += cf[i + 1]);
}
}
ll solve(){
int k = min(r / l, n);
return ll(l) * f[k + 1] - ll(r % l) * cf[k + 1];
}
}
void init(vector<int>P, vector<int>W){
swap(p, P);
swap(w, W);
n = p.size();
if(count(w.begin(), w.end(), 1) == n){
sub4::init();
subtask_id = 4;
}
else if(*max_element(w.begin(), w.end()) <= 1){
sub5::init();
subtask_id = 5;
}
else{
sub12367::init();
}
}
ll query(int L, int R){
l = L;
r = R;
if(subtask_id == 4){
return sub4::solve();
}
if(subtask_id == 5){
return sub5::solve();
}
return sub12367::solve();
}
