#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<long long>
#define vll vector<vector<long long>>
vll tree;
vl weights;
vl c;
vl parents;
vl w;
vl subs; // Aktuální součet v podstromu (S[i])
long long query(int L, int R){
ll n = tree.size();
c.assign(n, 0);
subs.assign(n, 0);
// Sety: {váha, id_vrcholu}. Používáme multiset, kdyby měly vrcholy stejnou váhu,
// ale set<pair> stačí, protože ID je unikátní.
vector<set<pair<ll, ll>>> sets(n);
// 1. Bottom-up průchod
for (ll i = n - 1; i >= 0; i--){
// a) Přidáme aktuální vrchol do setu kandidátů
sets[i].insert({w[i], i});
// Spočítáme aktuální S[i].
// Protože začínáme s C[i]=0, je S[i] rovno součtu S dětí.
ll current_sum = 0;
// b) Sloučení dětí (Small-to-Large Merging)
int biggest_child = -1;
size_t max_size = 0;
// První průchod: najít nejtěžšího syna a sečíst S
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;
}
}
}
// Přičteme vlastní C[i] (které je zatím 0, ale pro úplnost)
subs[i] = current_sum + c[i];
// Swap s největším
if (biggest_child != -1){
swap(sets[i], sets[biggest_child]);
}
// Dosypání ostatních
for (ll child : tree[i]){
if (child != parents[i] && child != biggest_child){
for (auto &item : sets[child]){
sets[i].insert(item);
}
sets[child].clear();
}
}
// === FÁZE 1: Doplňování do L (pokud je součet moc malý) ===
while (subs[i] < L) {
if (sets[i].empty()) break; // Nemělo by nastat
pair<ll, ll> best = *sets[i].begin();
ll u = best.second;
// Kolik potřebujeme přidat?
ll need = L - subs[i];
// Validace cesty nahoru: Můžeme přidat, aniž bychom porušili R?
// (Tato kontrola je nutná, pokud by přidání způsobilo, že nějaký potomek přeteče přes R.
// Většinou ale doplňujeme "díru", takže to projde. Ale formálně:)
ll limit_on_path = 2e18;
ll curr = u;
bool blocked = false;
while (true){
// Kolik místa zbývá do R?
if (subs[curr] >= R) { // Už jsme na hraně nebo přes
blocked = true;
break;
}
limit_on_path = min(limit_on_path, (ll)R - subs[curr]);
if (curr == i) break;
curr = parents[curr];
}
if (blocked || limit_on_path == 0) {
sets[i].erase(sets[i].begin()); // Tento vrchol už nemůžeme zvýšit
continue;
}
ll k = min(need, limit_on_path);
// Aplikace změny
c[u] += k;
curr = u;
while(true){
subs[curr] += k;
if (curr == i) break;
curr = parents[curr];
}
}
// === FÁZE 2: Ořezávání na R (pokud je součet moc velký) ===
while (subs[i] > R){
if (sets[i].empty()) break;
pair<ll, ll> best = *sets[i].begin();
ll u = best.second;
ll need = subs[i] - R;
// Validace cesty nahoru: Můžeme ubrat, aniž bychom podtekli pod L?
ll limit_on_path = 2e18;
ll curr = u;
bool blocked = false;
while (true){
if (subs[curr] <= L) {
blocked = true;
break;
}
limit_on_path = min(limit_on_path, subs[curr] - (ll)L);
if (curr == i) break;
curr = parents[curr];
}
if (blocked || limit_on_path == 0) {
sets[i].erase(sets[i].begin()); // Tento vrchol už nemůžeme snížit
continue;
}
ll k = min(need, limit_on_path);
c[u] -= k;
curr = u;
while(true){
subs[curr] -= k;
if (curr == i) break;
curr = parents[curr];
}
}
}
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]);
}
}
