#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
vll tree;
vl weights;
vl c;
vl parents;
vl w;
vl subs; // S[i] - aktuální součet v podstromu
long long query(int L, int R){
ll n = tree.size();
c.assign(n, 0);
subs.assign(n, 0);
// Pole setů. Každý set obsahuje pary {váha, id_vrcholu}.
// Používáme vector setů, abychom mohli dělat swap.
vector<set<pair<ll, ll>>> sets(n);
// 1. Inicializace listů
// Nastavíme C[i] = L pro listy. Ostatní vrcholy mají C[i] = 0.
// Subs (S[i]) se dopočítá v bottom-up průchodu.
for (ll i = 1; i < n; i++){
if (tree[i].size() == 1){
c[i] = L;
subs[i] = L;
}
}
// 2. Bottom-up průchod (od listů ke kořeni)
for (ll i = n - 1; i >= 0; i--){
// a) Vlastní váha a set
sets[i].insert({w[i], i});
ll current_sum = subs[i]; // Začínáme s tím, co už tam je (L pro listy, 0 jinak)
// b) Sloučení dětí (Small-to-Large Merging)
// Nejprve najdeme dítě s největším setem
int biggest_child = -1;
size_t max_size = 0;
// První průchod dětmi: spočítat sumu a najít největší set
for (ll child : tree[i]){
if (child != parents[i]){
current_sum += subs[child];
if (sets[child].size() > max_size){
max_size = sets[child].size();
biggest_child = child;
}
}
}
subs[i] = current_sum;
// Pokud máme nějaké děti, prohodíme set s tím největším
if (biggest_child != -1){
swap(sets[i], sets[biggest_child]);
}
// Druhý průchod dětmi: dosypeme prvky z malých setů do toho velkého (teď už sets[i])
for (ll child : tree[i]){
if (child != parents[i] && child != biggest_child){
for (auto &item : sets[child]){
sets[i].insert(item);
}
sets[child].clear(); // Uvolníme paměť (volitelné, ale dobré)
}
}
// c) Snižování součtu, dokud je S[i] > R
while (subs[i] > R){
if (sets[i].empty()) break; // Nemělo by nastat, pokud existuje řešení
// Vezmeme nejlevnější vrchol
pair<ll, ll> best = *sets[i].begin();
ll w_val = best.first;
ll u = best.second; // Vrchol, který chceme snížit
// VALIDACE & VÝPOČET K
// Musíme zjistit, o kolik maximálně můžeme snížit uzel 'u',
// aniž bychom porušili podmínku S[v] >= L na cestě od 'u' k 'i'.
ll max_decrease = subs[i] - R; // Potřebujeme snížit alespoň o tolik (resp. tolik chceme)
ll curr = u;
ll limit_on_path = 2e18; // Nekonečno
// Jdeme nahoru až k aktuálnímu vrcholu 'i'
while (true){
// Kolik zbývá místa do L v aktuálním bodě cesty?
limit_on_path = min(limit_on_path, subs[curr] - L);
if (curr == i) break;
curr = parents[curr];
}
// Pokud je limit 0, znamená to, že někde na cestě je uzel 'v', kde S[v] == L.
// Tento uzel 'u' už nikdy nepůjde snížit (pro tento podstrom).
if (limit_on_path == 0) {
sets[i].erase(sets[i].begin()); // Odstraníme ho a zkusíme další v příštím cyklu
continue;
}
// Určíme reálné snížení
ll k = min(max_decrease, limit_on_path);
// Aplikujeme změnu
c[u] -= k;
// Aktualizujeme S[] hodnoty na cestě
curr = u;
while (true){
subs[curr] -= k;
if (curr == i) break;
curr = parents[curr];
}
// Vrchol 'u' NEVYHAZUJEME hned, pokud jsme ho nevyčerpali úplně.
// Vyhodí se sám v příští iteraci (pomocí limit_on_path == 0),
// až narazí na dno L.
}
}
// Výpočet finální ceny
ll price = 0;
for (ll i = 0; i < n; i++){
price += w[i] * abs(c[i]);
}
return price;
}
void init(std::vector<int> P, std::vector<int> W){
weights.clear();
tree.clear();
parents.clear();
w.clear();
for (ll i = 0; i < W.size(); i++){ weights.push_back(W[i]); }
tree.resize(P.size());
for (ll i = 1; i < P.size(); i++){
tree[i].push_back(P[i]);
tree[P[i]].push_back(i);
}
for (ll i = 0; i < P.size(); i++){
parents.push_back(P[i]);
w.push_back(W[i]);
}
}
