#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N = 200200;
int n;
vector<int> p, w;
vector<int> adj[N];
ll cache;
ll c[N];
vector<ll> roots;
vector<ll> suf;
void dfs(int v) {
if (adj[v].empty()) cache += w[v], c[v] = 1;
for (int u : adj[v]) {
dfs(u);
c[v] += c[u];
}
if (w[v]==0) c[v] = 1;
if (v==0 || w[p[v]]==0) roots.pb(c[v]);
}
void init(std::vector<int> P, std::vector<int> W) {
n = P.size();
p = P;
w = W;
for (int i=1; i<n; i++) adj[p[i]].pb(i);
dfs(0);
sort(roots.begin(), roots.end());
suf = roots;
for (int i = int(suf.size()) - 2; 0 <= i; i--) suf[i] += suf[i+1];
}
long long query(int L, int R) {
ll ans = cache * L;
ll k = (R + L-1) / L;
int i = lower_bound(roots.begin(), roots.end(), k) - roots.begin();
if (i != roots.size()) ans += 1ll * L * suf[i] - 1ll * R * (roots.size() - i);
return ans;
}
