#include <bits/stdc++.h>
#include "tree.h"
#define ll long long
#define endl "\n"
using namespace std;
const ll N = 2e5 + 5;
int n;
vector<ll> g[N];
vector<ll> a, pa;
ll dp[N];
std::vector<int> p, w;
void dfs(ll v)
{
dp[v] = g[v].size() == 0;
for (ll to : g[v])
dfs(to), dp[v] += dp[to];
if (w[v] == 0)
{
for (ll to : g[v]) if (w[to]) a.push_back(dp[to]);
dp[v] = 1;
}
}
ll cnt = 0;
void init(std::vector<int> P, std::vector<int> W)
{
p = P;
n = p.size();
w = W;
w.insert(w.begin(), 0);
p.insert(p.begin(), 0);
for (ll i = 1; i <= n; i++)
{
p[i]++;
g[p[i]].push_back(i);
}
dfs(0);
for (ll i = 1; i <= n; i++)
if (!g[i].size())
cnt += w[i];
sort(a.begin(), a.end());
a.insert(a.begin(), 0);
pa.push_back(0);
for (ll i = 1; i < a.size(); i++) pa.push_back(pa.back() + a[i]);
}
long long query(int l, int r)
{
ll pos = lower_bound(a.begin(), a.end(), (r + l - 1) / l) - a.begin() - 1;
return (pa.back() - pa[pos]) * l + l * cnt - (pa.size() - pos - 1) * r;
}
