#include "tree.h"
#include <bits/stdc++.h>
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;
const int INF = 1e9 + 20;
template<typename T, T (*op)(const T&, const T&), T (*id)()>
struct SegTree {
int n;
vector<T> st;
SegTree(int _n = 0) : n(_n), st(2 * n, id()) {};
void init(vector<T> v) {
assert(sz(v) == n);
forn(i, n) st[i + n] = v[i];
dforsn(i, 1, n) st[i] = op(st[2 * i], st[2 * i + 1]);
}
T query(int l, int r) {
T lans = id(), rans = id();
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) lans = op(lans, st[l++]);
if (r & 1) rans = op(st[--r], rans);
}
return op(lans, rans);
}
void update(int p, T v) {
st[p += n] = v;
while (p /= 2) st[p] = op(st[2 * p], st[2 * p + 1]);
}
};
const int MAX_N = 2e5 + 9;
int in[MAX_N], out[MAX_N];
int w[MAX_N], t;
vi adj[MAX_N];
int n;
void dfs(int u) {
in[u] = t++;
for (int v : adj[u]) dfs(v);
out[u] = t;
}
void init(vi P, vi W) {
n = sz(P);
forsn(i, 1, n) adj[P[i]].pb(i);
forn(i, n) w[i] = W[i];
t = 0;
dfs(0);
}
ii minOp(const ii &a, const ii &b) { return min(a, b); }
ii minNeutr() { return ii{INF, INF}; }
template<typename T> T sumOp(const T &a, const T &b) { return a + b; }
template<typename T> T sumNeutr() { return 0; }
ll query(int L, int R) {
SegTree<ii, minOp, minNeutr> mini(n);
vector<ii> a(n);
forn(u, n) a[in[u]] = {w[u], u};
mini.init(a);
SegTree<ll, sumOp, sumNeutr> sum(n);
SegTree<int, sumOp, sumNeutr> cnt(n + 1);
ll ret = 0LL;
dforn(u, n) {
if (adj[u].empty()) {
sum.update(in[u], L);
mini.update(in[u], minNeutr());
ret += 1LL * w[u] * L;
continue;
}
ll currSum = sum.query(in[u], out[u]);
while (currSum > R) {
auto [_, v] = mini.query(in[u], out[u]);
if (cnt.query(0, in[v] + 1) > 0) {
mini.update(in[v], minNeutr());
continue;
}
ll sumV = sum.query(in[v], out[v]);
ll need = min(currSum - R, sumV - L);
currSum -= need;
sum.update(in[v], sum.st[in[v] + n] - need);
ret += 1LL * w[v] * need;
if (sumV - need == L) {
cnt.update(in[v], cnt.st[in[v] + cnt.n] + 1);
cnt.update(out[v], cnt.st[out[v] + cnt.n] - 1);
}
}
}
return ret;
}
