#include <bits/stdc++.h>
#include "tree.h"
using namespace std;
using ll = long long;
const ll INF = 1'000'000'000'000'000'000LL;
const ll ssz = 524288;
ll n;
vector<ll> p, w;
vector<vector<ll>> adj;
vector<bool> is_leaf;
vector<ll> LL, RR;
vector<pair<ll, ll>> special_pairs;
ll T = 0;
ll leaf_sum = 0;
vector<ll> seg_leaf(2 * ssz, 0);
vector<pair<ll, ll>> seg_weight(2 * ssz, {INF, -1});
vector<ll> Rx, Lx;
void add_leaf(ll i, ll x) {
i += ssz;
seg_leaf[i] = x;
for (i /= 2; i > 0; i /= 2)
seg_leaf[i] = seg_leaf[2 * i] + seg_leaf[2 * i + 1];
}
ll sum_leaf(ll l, ll r) {
l += ssz; r += ssz;
ll ans = 0;
while (l <= r) {
if (l % 2 == 1) ans += seg_leaf[l++];
if (r % 2 == 0) ans += seg_leaf[r--];
l /= 2; r /= 2;
}
return ans;
}
void upd_weight(ll i, pair<ll, ll> x) {
i += ssz;
seg_weight[i] = x;
for (i /= 2; i > 0; i /= 2)
seg_weight[i] = min(seg_weight[2 * i], seg_weight[2 * i + 1]);
}
pair<ll, ll> min_val(ll l, ll r) {
l += ssz; r += ssz;
pair<ll, ll> ans = {INF, -1};
while (l <= r) {
if (l % 2 == 1) ans = min(ans, seg_weight[l++]);
if (r % 2 == 0) ans = min(ans, seg_weight[r--]);
l /= 2; r /= 2;
}
return ans;
}
void dfs1(ll u) {
is_leaf[u] = true;
LL[u] = T++;
for (ll v : adj[u]) {
is_leaf[u] = false;
dfs1(v);
}
if (is_leaf[u]) {
leaf_sum += w[u];
w[u] = INF;
}
RR[u] = T - 1;
}
void dfs(ll u, ll sub) {
if (is_leaf[u]) {
is_leaf[u] = false;
add_leaf(LL[u], 0);
return;
}
auto [min_weight, index] = min_val(LL[u], RR[u]);
special_pairs.push_back({min_weight - sub, sum_leaf(LL[u], RR[u])});
sub = min_weight;
for (ll v : adj[index])
dfs(v, sub);
is_leaf[index] = true;
add_leaf(LL[index], 1);
upd_weight(LL[index], {INF, index});
w[index] = INF;
dfs(u, sub);
}
void init(vector<signed> P, vector<signed> W) {
n = P.size();
p.resize(n);
w.resize(n);
for (ll i = 0; i < n; ++i) {
p[i] = P[i];
w[i] = W[i];
}
adj.assign(n, {});
for (ll i = 1; i < n; ++i)
adj[p[i]].push_back(i);
is_leaf.assign(n, false);
LL.assign(n, 0);
RR.assign(n, 0);
T = 0;
leaf_sum = 0;
dfs1(0);
for (ll i = 0; i < n; i++) {
if (is_leaf[i]) add_leaf(LL[i], 1);
upd_weight(LL[i], {w[i], i});
}
dfs(0, 0);
Rx.assign(n + 1, 0);
Lx.assign(n + 1, 0);
Lx[0] = leaf_sum;
for (auto& [wt, c] : special_pairs) {
Lx[1] += c * wt;
Lx[c + 1] -= c * wt;
Rx[1] -= wt;
Rx[c + 1] += wt;
}
for (ll i = 1; i <= n; ++i) {
Lx[i] += Lx[i - 1];
Rx[i] += Rx[i - 1];
}
}
ll query(signed L, signed R) {
if (L == 0) return 0;
ll k = (R + L - 1) / L;
return L * Lx[k] + R * Rx[k];
}
