#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
int 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];
void endComp(int l, int w) {
coefL[l] += (long long)l * w;
coefR[l] -= w;
}
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 = p.size();
for (int v = 1; v < n; v++)
adj[p[v]].push_back(v);
vector<pair<int, int>> ord;
for (int v = 0; v < n; v++) {
if (adj[v].empty())
coefL[n] += w[v];
else
ord.push_back({w[v], v});
sef[v] = v;
leaves[v] = 1;
minW[v] = w[v];
}
sort(ord.begin(), ord.end());
reverse(ord.begin(), ord.end());
for (auto pp: ord) {
int u = pp.second;
int a = findSef(u);
endComp(leaves[a], minW[a] - w[u]);
for (int v: adj[u]) {
endComp(leaves[v], minW[v] - w[u]);
leaves[a] += leaves[v];
sef[v] = a;
}
minW[a] = w[u];
leaves[a]--;
}
endComp(leaves[0], minW[0]);
for (int i = n - 1; i >= 0; i--) {
coefL[i] += coefL[i + 1];
coefR[i] += coefR[i + 1];
}
}
long long query(int l, int r) {
int k = min(n, r / l + 1);
return l * coefL[k] + r * coefR[k];
}
