#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 200005;
int N;
vt<int> P, W, adj[mxN];
int hson[mxN], szs[mxN];
int tin[mxN], tout[mxN], head[mxN], timer, rev_tin[mxN];
struct Node {
ll mss;
ari2 min_w;
ll lz;
Node operator+(const Node &other) {
return {min(mss, other.mss), min(min_w, other.min_w), 0};
}
} st[mxN<<2];
#define lc i << 1
#define rc lc | 1
void build(const int i = 1, const int tl = 0, const int tr = N-1) {
if (tl == tr)
st[i] = {LLONG_MAX, ari2{W[rev_tin[tl]], rev_tin[tl]}, 0};
else {
const int tm = tl + tr >> 1;
build(lc, tl, tm);
build(rc, tm+1, tr);
st[i] = st[lc] + st[rc];
}
}
void app(const int i, const ll lz) {
st[i].mss += lz;
st[i].lz += lz;
}
void push(const int i) {
if (st[i].lz == 0)
return;
app(lc, st[i].lz);
app(rc, st[i].lz);
st[i].lz = 0;
}
void update_add(const int ql, const int qr, const ll v, const int i = 1, const int tl = 0, const int tr = N-1) {
if (tl > qr || tr < ql)
return;
if (ql <= tl && tr <= qr)
app(i, v);
else {
push(i);
const int tm = tl + tr >> 1;
update_add(ql, qr, v, lc, tl, tm);
update_add(ql, qr, v, rc, tm+1, tr);
st[i] = st[lc] + st[rc];
}
}
void update_set(const int p, const int i = 1, const int tl = 0, const int tr = N-1) {
if (tl == tr)
st[i].min_w = {INT_MAX, -1};
else {
push(i);
const int tm = tl + tr >> 1;
if (p <= tm)
update_set(p, lc, tl, tm);
else
update_set(p, rc, tm+1, tr);
st[i] = st[lc] + st[rc];
}
}
void update_mss(const int p, const ll v, const int i = 1, const int tl = 0, const int tr = N-1) {
if (tl == tr)
st[i].mss = v;
else {
push(i);
const int tm = tl + tr >> 1;
if (p <= tm)
update_mss(p, v, lc, tl, tm);
else
update_mss(p, v, rc, tm+1, tr);
st[i] = st[lc] + st[rc];
}
}
Node query_path(const int ql, const int qr, const int i = 1, const int tl = 0, const int tr = N-1) {
if (tl > qr || tr < ql)
return {LLONG_MAX, ari2{INT_MAX, -1}, LLONG_MAX};
if (ql <= tl && tr <= qr)
return st[i];
push(i);
const int tm = tl + tr >> 1;
return query_path(ql, qr, lc, tl, tm) + query_path(ql, qr, rc, tm+1, tr);
}
#undef lc
#undef rc
ll worst(int i) {
ll ret = LLONG_MAX;
for (; i >= 0; i = P[head[i]])
ret = min(ret, query_path(tin[head[i]], tin[i]).mss);
return ret;
}
void update_path(int i, const ll v) {
for (; i >= 0; i = P[head[i]])
update_add(tin[head[i]], tin[i], v);
}
ll query(int L, int R) {
ll ans = 0;
build();
const auto dfs = [&](auto &&self, const int i) -> int {
if (tin[i] == tout[i]) {
ans += 1ll * L * W[i];
update_set(tin[i]);
return L;
}
ll cur_sum = 0;
for (const auto &j : adj[i])
cur_sum += self(self, j);
//cout << worst(0) << ' ' << cur_sum << ' ' << R << '\n';
while (cur_sum > R) {
const auto [w, k] = query_path(tin[i], tout[i]).min_w;
ll v = worst(k);
assert(k >= 0 && v >= L);
ans += 1ll * w * min(cur_sum - R, v - L);
update_path(k, -min(cur_sum - R, v - L));
cur_sum -= min(cur_sum - R, v - L);
v -= min(cur_sum - R, v - L);
if (v == L)
update_set(tin[k]);
}
update_mss(tin[i], cur_sum);
return cur_sum;
};
dfs(dfs, 0);
return ans;
}
void dfs_szs(const int i) {
szs[i] = 1;
hson[i] = -1;
for (const auto &j : adj[i]) {
dfs_szs(j);
szs[i] += szs[j];
if (hson[i] < 0 || szs[j] > szs[hson[i]])
hson[i] = j;
}
}
void dfs_hld(const int i) {
rev_tin[tin[i] = timer++] = i;
if (hson[i] >= 0) {
head[hson[i]] = head[i];
dfs_hld(hson[i]);
}
for (const auto &j : adj[i])
if (j != hson[i]) {
head[j] = j;
dfs_hld(j);
}
tout[i] = timer - 1;
}
void init(vt<int> _P, vt<int> _W) {
P = _P, W = _W, N = size(P);
FOR(i, 1, N-1)
adj[P[i]].push_back(i);
dfs_szs(0);
dfs_hld(0);
}
