#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
int n;
int parent[MAX_N], w[MAX_N], perm[MAX_N];
int sef[MAX_N], leaves[MAX_N], minW[MAX_N];
long long coefL[MAX_N + 1], coefR[MAX_N + 1];
vector<int> adj[MAX_N];
int findSef(int v) {
if (sef[v] != v)
sef[v] = findSef(sef[v]);
return sef[v];
}
void init(vector<int> P, vector<int> W) {
n = (int)W.size();
for (int v = 0; v < n; v++) {
parent[v] = P[v];
if (v != 0)
adj[parent[v]].push_back(v);
w[v] = W[v];
}
for (int i = 0; i < n; i++)
perm[i] = i;
sort(perm, perm + n, [](int u, int v) { return w[u] < w[v]; });
for (int v = 0; v < n; v++) {
sef[v] = v;
leaves[v] = 1;
minW[v] = w[v];
}
for (int i = n - 1; i >= 0; i--) {
int u = perm[i];
if (adj[u].empty()) {
coefL[n] += w[u];
continue;
}
int a = findSef(u);
coefL[leaves[a]] += (long long)(minW[a] - w[u]) * leaves[a];
coefR[leaves[a]] -= minW[a] - w[u];
for (int v: adj[u]) {
int b = findSef(v);
sef[b] = a;
leaves[a] += leaves[b];
//printf("%d %d %d %d %d\n", u, b, leaves[b], minW[b], w[u]);
coefL[leaves[b]] += (long long)(minW[b] - w[u]) * leaves[b];
coefR[leaves[b]] -= minW[b] - w[u];
}
minW[a] = w[u];
leaves[a]--;
}
coefL[leaves[0]] += (long long)minW[0] * leaves[0];
coefR[leaves[0]] -= minW[0];
int b = findSef(0);
//printf("%d %d %d\n", b, leaves[b], minW[b]);
for (int i = n - 1; i >= 0; i--) {
coefL[i] += coefL[i + 1];
coefR[i] += coefR[i + 1];
}
//for (int i = 0; i <= n; i++)
// printf("%lld %lld\n", coefL[i], coefR[i]);
}
long long query(int l, int r) {
int k = min(n, r / l + 1);
return l * coefL[k] + r * coefR[k];
}
