#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int SZ = 1001000;
int n;
vector<int> adj[200200], buf[SZ+2];
ll a[200200], suf1[SZ+2], suf2[SZ+2], sum;
struct DSU{
int path[200200], rt[200200];
ll sum[200200];
void init(int n){
for (int i=1;i<=n;i++) path[i] = i, rt[i] = SZ + 1;
}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
void toggle(int x, int t, ll v){
assert(rt[x] == SZ+1);
rt[x] = t;
sum[x] = v;
}
void push(int x, int t){
x = find(x);
suf1[sum[x]] += sum[x] * (rt[x] - t);
suf2[sum[x]] += rt[x] - t;
rt[x] = t;
}
void merge(int x, int y, int t){
x = find(x);
y = find(y);
if (rt[x]==SZ+1 || rt[y]==SZ+1) return;
push(x, t);
push(y, t);
if (x==y) return;
path[x] = y;
sum[y] += sum[x];
}
}dsu;
void init(std::vector<int> P, std::vector<int> W) {
n = P.size();
for (int i=1;i<n;i++) adj[P[i]+1].push_back(i+1);
for (int i=0;i<n;i++) a[i+1] = W[i];
for (int i=1;i<=n;i++) if (adj[i].empty()) sum += a[i];
dsu.init(n);
for (int i=1;i<=n;i++) if (!adj[i].empty()) buf[a[i]].push_back(i);
for (int t=SZ-1;t>=0;t--){
for (auto &x:buf[t]){
dsu.toggle(x, t, max((int)adj[x].size() - 1, 0));
dsu.merge(x, P[x-1]+1, t);
for (auto &y:adj[x]) dsu.merge(x, y, t);
}
}
dsu.push(1, 0);
for (int i=SZ;i>=0;i--) suf1[i] += suf1[i+1], suf2[i] += suf2[i+1];
}
long long query(int L, int R) {
return sum * L + suf1[(R-L) / L + 1] * L - suf2[(R-L) / L + 1] * (R-L);
}
