#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;
bool done[MAX_N];
vi adj[MAX_N];
int n;
bool only0and1;
void dfs0(int u) {
in[u] = t++;
for (int v : adj[u]) dfs0(v);
out[u] = t;
}
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; }
SegTree<ii, minOp, minNeutr> mini;
SegTree<int, sumOp, sumNeutr> sum;
vector<ii> terms;
ll sumOfLeafs;
vector<ll> prefA, prefB;
void solve(int u, int delta) {
while (true) {
auto [minW, v] = mini.query(in[u], out[u]);
if (minW == INF) {
sum.updateSet(in[u], 0);
done[u] = true;
return;
}
int leafs = sum.query(in[u], out[u]);
terms.eb(leafs, minW - delta);
delta = minW;
for (int c : adj[v]) {
if (!done[c]) solve(c, delta);
}
sum.updateSet(in[v], 1);
mini.updateSet(in[v], ii{INF, -1});
}
}
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;
dfs0(0);
vector<ii> v(n);
vi c(n);
mini = SegTree<ii, minOp, minNeutr>(n);
sum = SegTree<int, sumOp, sumNeutr>(n);
forn(u, n) {
if (out[u] - in[u] == 1) {
v[in[u]] = {INF, u}, c[in[u]] = 1;
sumOfLeafs += w[u];
} else {
v[in[u]] = {w[u], u}, c[in[u]] = 0;
}
}
mini.init(v), sum.init(c);
solve(0, 0);
sort(all(terms));
prefA.resize(sz(terms) + 1);
prefB.resize(sz(terms) + 1);
prefA[0] = 0, prefB[0] = 0;
forn(i, sz(terms)) {
prefA[i + 1] = prefA[i] + 1LL * terms[i].fst * terms[i].snd;
prefB[i + 1] = prefB[i] - terms[i].snd;
}
}
ll query(int L, int R) {
int lo = -1, hi = sz(terms);
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (1LL * terms[mid].fst * L - R > 0) hi = mid;
else lo = mid;
}
return sumOfLeafs * L + (prefA.back() - prefA[hi]) * L + (prefB.back() - prefB[hi]) * R;
}
