#include "tree.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<vector<int>>adj;
vector<int>cnt;
int sum=0,n;
vector<int>v,pref;
void init(std::vector<int> P, std::vector<int> W) {
n=P.size();
adj.resize(n);
for(int i=1;i<n;i++){
adj[P[i]].push_back(i);
}
cnt.resize(n,0);
for(int i=0;i<n;i++)if(adj[i].empty()){
cnt[i]=1;
if(W[i]==1)sum++;
}
for(int i=n-1;i>0;i--){
cnt[P[i]]+=cnt[i];
if(W[P[i]]==0){
cnt[P[i]]=1;
if(W[i]==1)v.push_back(cnt[i]);
}
}
if(W[0]==1)v.push_back(cnt[0]);
sort(v.begin(),v.end());
pref.resize(v.size()+1);
pref[0]=0;
for(int i=1;i<pref.size();i++)pref[i]=pref[i-1]+v[i-1];
}
long long query(int L, int R) {
int idx=lower_bound(v.begin(),v.end(),R/L+1)-v.begin();
return (ll)sum*L+(ll)(pref.back()-pref[idx])*L-(ll)(v.size()-idx)*R;
}
