#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll INF = (ll)4e18;
struct Seg {
struct Node {
int k;
ll sum;
ll mnw;
int mni;
};
int n;
vector<Node> st;
vector<char> lz;
Node neu() { return {0, 0, INF, -1}; }
Node merge(const Node& a, const Node& b) {
Node r;
r.k = a.k + b.k;
r.sum = a.sum + b.sum;
if (a.mnw <= b.mnw) { r.mnw = a.mnw; r.mni = a.mni; }
else { r.mnw = b.mnw; r.mni = b.mni; }
return r;
}
Seg(int n=0): n(n) {
st.assign(4*n+5, neu());
lz.assign(4*n+5, 0);
}
void apply_del(int p) { st[p] = neu(); lz[p] = 1; }
void push(int p) {
if (!lz[p]) return;
apply_del(p<<1);
apply_del(p<<1|1);
lz[p] = 0;
}
void build(int p, int l, int r, const vector<int>& pos2v, const vector<ll>& W, const vector<char>& isLeaf) {
if (l == r) {
int v = pos2v[l];
if (isLeaf[v]) st[p] = {1, W[v], INF, -1};
else st[p] = {0, 0, W[v], v};
return;
}
int m = (l+r)>>1;
build(p<<1, l, m, pos2v, W, isLeaf);
build(p<<1|1, m+1, r, pos2v, W, isLeaf);
st[p] = merge(st[p<<1], st[p<<1|1]);
}
Node query(int p, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return neu();
if (ql <= l && r <= qr) return st[p];
push(p);
int m = (l+r)>>1;
return merge(query(p<<1, l, m, ql, qr), query(p<<1|1, m+1, r, ql, qr));
}
void delRange(int p, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) { apply_del(p); return; }
push(p);
int m = (l+r)>>1;
delRange(p<<1, l, m, ql, qr);
delRange(p<<1|1, m+1, r, ql, qr);
st[p] = merge(st[p<<1], st[p<<1|1]);
}
void setLeafZero(int p, int l, int r, int idx) {
if (l == r) { st[p] = {1, 0, INF, -1}; lz[p] = 0; return; }
push(p);
int m = (l+r)>>1;
if (idx <= m) setLeafZero(p<<1, l, m, idx);
else setLeafZero(p<<1|1, m+1, r, idx);
st[p] = merge(st[p<<1], st[p<<1|1]);
}
};
static int N;
static vector<int> P;
static vector<ll> W;
static vector<vector<int>> ch;
static vector<char> isLeaf;
static ll leafSum;
static int totalLeaves;
static vector<int> tin, tout, pos2v;
static int timer_;
static Seg seg;
static vector<ll> addW, addKW, sufW, sufKW, Acoef, Bcoef;
static void dfs(int v) {
tin[v] = timer_;
pos2v[timer_] = v;
timer_++;
for (int u : ch[v]) dfs(u);
tout[v] = timer_ - 1;
}
static void solve_sub(int root, ll offset) {
while (true) {
auto got = seg.query(1, 0, N-1, tin[root], tout[root]);
if (got.mnw >= INF/2) return;
int k = got.k;
int v = got.mni;
ll wprime = got.mnw - offset;
if (wprime < 0) wprime = 0;
addW[k] += wprime;
addKW[k] += wprime * (ll)k;
ll newOffset = offset + wprime;
for (int u : ch[v]) {
solve_sub(u, newOffset);
seg.delRange(1, 0, N-1, tin[u], tout[u]);
}
seg.setLeafZero(1, 0, N-1, tin[v]);
offset = newOffset;
}
}
void init(vector<int> _P, vector<int> _W) {
P = _P;
N = (int)P.size();
W.assign(N, 0);
for (int i = 0; i < N; i++) W[i] = (ll)_W[i];
ch.assign(N, {});
int root = 0;
for (int i = 0; i < N; i++) {
if (P[i] == -1) root = i;
else ch[P[i]].push_back(i);
}
isLeaf.assign(N, 0);
leafSum = 0;
totalLeaves = 0;
for (int i = 0; i < N; i++) {
if (ch[i].empty()) {
isLeaf[i] = 1;
leafSum += W[i];
totalLeaves++;
}
}
tin.assign(N, 0);
tout.assign(N, 0);
pos2v.assign(N, 0);
timer_ = 0;
dfs(root);
seg = Seg(N);
seg.build(1, 0, N-1, pos2v, W, isLeaf);
addW.assign(N+2, 0);
addKW.assign(N+2, 0);
solve_sub(root, 0);
sufW.assign(N+3, 0);
sufKW.assign(N+3, 0);
for (int k = N; k >= 0; k--) {
sufW[k] = sufW[k+1] + addW[k];
sufKW[k] = sufKW[k+1] + addKW[k];
}
Acoef.assign(N+2, 0);
Bcoef.assign(N+2, 0);
for (int t = 0; t <= N; t++) {
Acoef[t] = leafSum + sufKW[t+1];
Bcoef[t] = -sufW[t+1];
}
}
long long query(int L, int R) {
ll LL = (ll)L, RR = (ll)R;
int t = (int)(RR / LL);
if (t > N) t = N;
return Acoef[t] * LL + Bcoef[t] * RR;
}
