#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 updateSet(int p, T v) {
st[p += n] = v;
while (p /= 2) st[p] = op(st[2 * p], st[2 * p + 1]);
}
void updateAdd(int p, T v) {
p += n;
st[p] = op(st[p], 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;
bool only0and1;
void dfs(int u) {
in[u] = t++;
for (int v : adj[u]) dfs(v);
out[u] = t;
}
vi trees;
vi pref;
int dfs2(int u) {
if (w[u] == 0 || adj[u].empty()) {
for (int v : adj[u]) trees.pb(dfs2(v));
return w[u];
}
int leafs = 0;
for (int v : adj[u]) leafs += dfs2(v);
return leafs;
}
void init(vi P, vi W) {
n = sz(P);
forsn(i, 1, n) adj[P[i]].pb(i);
only0and1 = true;
forn(i, n) w[i] = W[i], only0and1 &= W[i] <= 1;
t = 0;
dfs(0);
trees.pb(dfs2(0));
sort(all(trees));
pref.resize(sz(trees) + 1);
pref[0] = 0;
forn(i, sz(trees)) pref[i + 1] = pref[i] + trees[i];
}
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) {
if (only0and1) {
int lo = -1, hi = sz(trees);
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (1LL * trees[mid] * L - R > 0) hi = mid;
else lo = mid;
}
return 1LL * pref.back() * L + 1LL * (pref.back() - pref[hi]) * L - 1LL * (sz(trees) - hi) * 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.updateAdd(in[u], L);
mini.updateSet(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.updateSet(in[v], minNeutr());
continue;
}
ll sumV = sum.query(in[v], out[v]);
ll need = min(currSum - R, sumV - L);
currSum -= need;
sum.updateAdd(in[v], -need);
ret += 1LL * w[v] * need;
if (sumV - need == L) {
cnt.updateAdd(in[v], +1);
cnt.updateAdd(out[v], -1);
}
}
}
return ret;
}
