#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> sef;
vector<long long> coefL, coefR;
void endComponent(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 = w.size();
coefL.resize(n + 1);
coefR.resize(n + 1);
vector<vector<int>> adj(n);
for (int v = 1; v < n; v++)
adj[p[v]].push_back(v);
vector<pair<int, int>> order;
vector<int> leaves(n), minW(n);
sef.resize(n);
for (int v = 0; v < n; v++) {
if (adj[v].empty())
coefL[n] += w[v];
else
order.push_back({w[v], v});
sef[v] = v;
leaves[v] = 1;
minW[v] = w[v];
}
sort(order.begin(), order.end());
reverse(order.begin(), order.end());
for (auto pp: order) {
int u = pp.second;
int a = findSef(u);
endComponent(leaves[a], minW[a] - w[u]);
for (int v: adj[u]) {
endComponent(leaves[v], minW[v] - w[u]);
leaves[a] += leaves[v];
sef[v] = a;
}
minW[a] = w[u];
leaves[a]--;
}
endComponent(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];
}
