#include "tree.h"
// ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
// Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * (b / gcd(a, b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) \
for (int w = 0; w < array.size(); w++) \
cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
int n;
std::vector<int> p, w;
vi cnt;
ll leaf = 0;
int dfs(vii &adj, int i, vi &W)
{
if (adj[i].size() == 0)
{
leaf++;
return 1;
}
int c = 0;
for (auto x : adj[i])
{
c += dfs(adj, x, W);
}
if (W[i] == 0)
{
cnt[c]++;
return 1;
}
else
{
return c;
}
}
void init(std::vector<int> P, std::vector<int> W)
{
n = P.size();
cnt.resize(n + 5);
vii adj(n + 1);
for (int i = 1; i < n; i++)
adj[P[i]].push_back(i);
cnt[dfs(adj, 0, W)]++;
for (int i = 1; i <= n; i++)
cnt[i] += cnt[i - 1];
}
long long query(int L, int R)
{
ll l = L, r = R;
ll cost = (leaf * l) + (max(0LL, (leaf * l)));
int k = R/L;
cost -= cnt[n]*(l);
cost += cnt[k]*l + (r*(cnt[n]-cnt[k]));
return cost;
}
