#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, INF = 1e9;
int n;
vector<int> adj[maxn];
int fa[maxn], w[maxn];
int leaf = 0;
int sz;
vector<pair<int,int>> vec = {{0, 0}};
int dfs(int u) {
if (w[u] && !adj[u].size()) leaf++;
if (w[u] == 0 || !adj[u].size()) return 1;
int cnt = 0;
for (int v:adj[u]) cnt += dfs(v);
return cnt;
}
void init(vector<int32_t> P, vector<int32_t> W) {
n = P.size();
for (int i=1;i<n;i++) adj[P[i]].push_back(i), fa[i] = P[i];
for (int i=0;i<n;i++) w[i] = W[i];
for (int i=0;i<n;i++) if ((i == 0 || w[fa[i]] == 0) && w[i]) {
int val = dfs(i);
vec.push_back({val, val});
}
vec.push_back({INF, 0});
sort(vec.begin(), vec.end());
sz = vec.size();
for (int i=1;i<sz;i++) vec[i].second += vec[i-1].second;
// for (auto [x, y]:vec) cout << x << " " << y << endl;
}
long long query(int32_t L, int32_t R) {
int l = 0, r = sz-1;
while (l < r) {
int mid = (l+r)/2;
if (L * vec[mid].first - R >= 0) r = mid;
else l = mid+1;
}
return L * (vec[sz-1].second - vec[l-1].second) - R * ((sz-2) - l + 1) + leaf * L;
}
