#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"
template<typename T> bool maximize(T &res, const T &val) {if(res > val) return 0; res = val; return 1;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int N = 2e5 + 3;
const int LOG = 20;
const int LIM = 1e6 + 3;
int n, m;
int par[N], num_leaf[N], leaf[N], num_wleaf[N], wei[N];
ll f[LIM], sum[LIM];
void init(int n, const vector<int> &w)
{
for(int i = 0; i < n; ++i)
{
par[i] = i;
num_leaf[i] = 1;
leaf[i] = 1;
num_wleaf[i] = wei[i] = w[i];
}
}
int root(int u) {return u == par[u] ? u : par[u] = root(par[u]);}
void union_set(int u, int v)
{
int pu = root(u), pv = root(v);
num_leaf[pu] += num_leaf[pv] - leaf[u];
num_wleaf[pu] += num_wleaf[pv] - leaf[u] * wei[u];
leaf[u] = 0;
par[pv] = pu;
}
ll tot_wleaf = 0;
void init(std::vector<int> P, std::vector<int> W)
{
n = sz(P);
init(n, W);
for(int i = 1; i < n; ++i)
{
if(W[P[i]] == 1)
union_set(P[i], i);
}
for(int i = 0 ; i < n; ++i) if(root(i) == i)
{
tot_wleaf += num_wleaf[i];
++f[num_leaf[i] - 1];
}
for(int i = 1e6; i >= 0; --i) f[i] += f[i + 1];
for(int i = 1e6; i >= 0; --i) sum[i] = sum[i + 1] + f[i];
}
ll query(int L, int R)
{
return 1ll * tot_wleaf * L + (1ll * sum[R / L] * L - 1ll * f[R / L] * (R % L));
}
