#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 life_lst[N], par[N], num_leaf[N], leaf[N], num_wleaf[N], wei[N];
ll f[LIM], sum[LIM];
int Maxx = 0;
ll tot_wleaf = 0;
void init(int n)
{
for(int i = 0; i < n; ++i)
{
par[i] = i;
num_leaf[i] = 1;
leaf[i] = 1;
life_lst[i] = Maxx - 1;
}
}
int root(int u) {return u == par[u] ? u : par[u] = root(par[u]);}
void update(int u, int w)
{
tot_wleaf += 1ll * num_wleaf[u] * w;
f[num_leaf[u] - 1] += w;
}
void make_1(int u, int lst)
{
int pu = root(u);
update(pu, life_lst[pu] - lst);
num_wleaf[pu] += 1;
wei[u] = 1;
life_lst[pu] = lst;
}
void union_set(int u, int v, int lst)
{
int pu = root(u), pv = root(v);
update(pu, life_lst[pu] - lst);
update(pv, life_lst[pv] - lst);
num_leaf[pu] += num_leaf[pv] - leaf[u];
num_wleaf[pu] += num_wleaf[pv] - leaf[u] * wei[u];
leaf[u] = 0;
par[pv] = pu;
life_lst[pu] = lst;
}
vector<int> g[N];
void init(std::vector<int> P, std::vector<int> W)
{
n = sz(P);
init(n);
for(int i = 0; i < n; ++i) maximize(Maxx, W[i]);
vector<pii> X;
for(int i = 0; i < n; ++i)
X.pb({W[i], i});
for(int i = 1; i < n; ++i) g[P[i]].pb(i);
sort(all(X));
for(int i = n - 1; i >= 0; --i)
{
int u = X[i].se;
make_1(u, W[u] - 1);
for(int v : g[u]) union_set(u, v, W[u] - 1);
}
for(int i = 0; i < n; ++i)
if(root(i) == i) update(i, life_lst[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));
}
