Zadanie

Po výbornom farmárskom výkone v minulom kole, sa aj Farmári z Matfyzu vybrali na výlet do Legolandu. Po tom ako sa pár krát stratili v spleti uličiek, jeden zavelil: “Kašlime na to. Spravme z Legolandu strom, nech sa tu nedá zablúdiť.” Rozhodli sa teda, že niektoré cesty v Legolande zastavajú tak aby vznikol strom. Chvíľu rozmýšlali či to spravili optimálne, ale zrazu sa vyskytol oveľa väčší problém.

V Legolande je zopár divných dier v časopriestore, ktoré fungujú takto: Po tom čo kozmickej bytosti zaplatíš \(c\) vesmírnych peňazí, ocitneš sa o \(w\) sekúnd v mieste, kde sa diera nachádza a to bez ohladu na to, kde si sa predtým nachádzal. Toto Farmárom otvorilo nové možnosti prepravovania sa v Legolande a teraz ich zaujíma, ako sa vedia za nejaký čas dostať z vchodu do Legolandu napríklad do miestnej lego farmy, alebo na najbližší burger. Keďže však sú študenti, potrebujú to spraviť za čo najmenej vesmírnych peňazí, aby im to ešte fakulta preplatila. Farmári nie sú moc dobrí programátori, preto niet divu, že táto úloha pripadla na vás.

Úloha

Legoland je strom, teda súvislý graf s \(n\) vrcholmi a \(n - 1\) hranami. Vstup do Legolandu, kde sa nachádzajú Farmári teraz, je vo vrchole \(0\), v tomto vrchole strom zakoreníme. Pre každú hranu \(i\) vieme číslo \(t_i\) – čas v sekundách, ktorý trvá prejsť ju Farmárom peši.

V Legolande je \(m \leq n\) dier v časopriestore. Diera \(i\) sa nachádza vo vrchole \(v_i \leq n\) a poznáme pre ňu ešte 2 hodnoty: \(c_i\) – cena, ktorú musia Farmári zaplatiť kozmickej bytosti, a \(w_i\) – čas v sekundách, ktorý musia Farmári čakať, kým sa premiestnia do vrcholu \(v_i\). Všimnite si, že to nezávisí od toho, kde sa práve Farmári nachádzajú (hovoril som, že diery v časopriestore sú divné?)

Farmári si vybrali \(q\) zaujímavých miest, \(a_1,\dots,a_q\) a na \(i\)-te z nich by sa chceli dostať z vrcholu \(0\) za \(b_i\) času. Vašou úlohou je zistiť, či a za koľko najmenej peňazí sa na miesto \(a_i\) vedia dostať v časovom limite \(b_i\).

Formát vstupu

Na prvom riadku vstupu je číslo \(T\) popisujúce počet testov. Nasleduje \(T\) testov, pred každým z nich je prázdny riadok.

Na prvom riadku testu je číslo \(n\) (\(1\leq n \leq 10^5\)) – počet vrcholov v strome.

Na druhom riadku je popis stromu: \(n - 1\) čísel \(p_1,\dots,p_{n-1}\) oddelených medzerou. Číslo \(p_i\) (\(0\leq p_i < i\)) popisuje, že otec vrcholu s číslom \(i\) je vrchol \(p_i\). (Vrcholy číslujeme od \(0\). Vrchol \(0\) nemá otca, lebo je koreň.) Je zaručené, že žiaden vrchol nemá za otca vrchol s väčším číslom.

Na treťom riadku sú zadané časy na prejdenie hrán: \(n - 1\) čísel \(t_1,\dots,t_{n-1}\) oddelených medzerou. Číslo \(t_i\) (\(1\leq t_i \leq 10^9\)) popisuje čas v sekundách, aký trvá prejdenie z vrcholu \(i\) do jeho otca (a naopak).

Na štvrtom riadku je číslo \(m\) (\(1\leq m\leq 10^5\)) – počet dier.

Nasleduje \(m\) riadkov, \(i\)-ty z nich obsahuje 3 čísla \(v_i, c_i, w_i\) oddelené medzerou (\(0\leq v_i < n\), \(1\leq c_i, w_i\leq 10^9\)): postupne vrchol v ktorom sa diera nachádza, cena vo vesmírnych peniazoch a čas v sekundách aký trvá kým sa do diery premiestnite (viac dier môže byť v tom istom vrchole)

Na nasledujúcom riadku je číslo \(q\) (\(1\leq q \leq 10^5\)) – počet otázok.

Nasleduje \(q\) riadkov. Na \(i\)-tom z nich sú 2 čísla \(a_i, b_i\) (\(0\leq a_i < n\), \(1\leq b_i \leq 10^9\)) – postupne vrchol, kam sa chcú Farmári dostať a ako najdlhšie to môže trvať.

Formát výstupu

Pre každú otázku vypíšte jeden riadok a v ňom jedno číslo – koľko najmenej peňazí musia Farmári použiť, na to aby sa dostali z vrcholu \(0\) do cieľa v časovom limite, prípadne \(-1\), ak sa tam v časovom limite dostať nevedia.

Hodnotenie

Sú 4 sady vstupov, za každú sú 2 body. Nech \(C\) označuje najväčšie z čísel na vstupe a \(H\) hĺbku stromu1, potom v jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
\(1 \leq n, q \leq\) \(1000\) \(10^5\) \(10^5\) \(10^5\)
\(1 \leq m \leq\) \(1000\) \(100\) \(10^5\) \(10^5\)
\(C \leq\) \(1000\) \(10^9\) \(10^9\) \(10^9\)
\(1 \leq H \leq\) \(n\) \(n\) \(100\) \(n\)

Súčet hodnôt \(n\) vo všetkých testoch nepresiahne \(10^5\). Rovnako aj súčet hodnôt \(m\) a \(q\).

Príklady

Input:

1

2
0
2
1
1 1 1
2
1 2
1 1

Output:

0
1

Pri prvej otázke sa dá v časovom limite prejsť do cieľa peši, preto je odpoveď 0. Pri druhej otázke musíme použiť dieru vo vrchole 1, tá má cenu 1.

Input:

2

5
0 1 2 3
4 7 8 6
3
0 7 3
4 2 3
2 1 10
3
3 7
4 14
2 10

5
0 0 2 1
3 1 3 4
2
4 6 2
4 3 3
3
4 2
4 3
4 7

Output:

-1
2
1
6
3
0

Táto úloha mala veľmi nechutne dlhé zadanie. Ak ste sa však nenechali odradiť ani dĺžkou zadania ani číslom úlohy, riešenie na 4 body nebolo vôbec ťažké. Pred tým ako sa bezhlavo pustíme do programovania, je užitočné si ťažkú úlohu čo najviac zľahčiť.

Základné pozorovania

Ako prvé sa zamyslime, ako si zjednodušiť úvahy s dierami.

Môžeme si uvedomiť, že ak sme najskorej chodili peši a potom použili nejakú dieru, mohli sme rovno použiť tú istú dieru a opäť, mali by sme aspoň rovnako dobré riešenie. Teda diery sa oplatí používať len na začiatku, keď sme vo vrchole \(0\).

Druhé pozorovanie je, že vždy sa nám oplatí použiť najviac jednu dieru. Ak by sme použili nejaké dve, najprv \(A\) a potom \(B\), mohli sme rovno použiť \(B\), a mali by sme aspoň také dobré riešenie ako doteraz. To vyplýva z toho, že nezáleží kde sa nachádzame, diera nás k sebe premiestni vždy rovnako rýchlo.

Posledné užitočné aj keď nie nutné je pridať si do vrcholu \(0\) fiktívnu dieru s časom \(0\) a cenou \(0\). To bude zodpovedať možnosti, kde nepoužijeme žiadnu dieru. Zvyšok vzoráku rátame s tým, že sme tento trik spravili.

Naraz sa nám úloha značne zjednodušila: Máme strom, v niektorých vrcholoch sú diery. Ak by sme chceli v \(i\)-tej otázke použiť \(j\)-tu dieru, vieme sa z nej pohnúť o vzdialenosť \(b_i - w_j\). Chceme teda vybrať dieru z najnižšou cenou, z ktorej sa vieme dostať do vrcholu \(a_i\).

Toto nám stačí na pohodlný bruteforce.

Bruteforce

Nasledovné riešenie mohlo získať 4 body:

Z každej diery spustíme prehľadávanie a tým pre každý vrchol spočítame vzdialenosti od všetkých dier. Potom pri query \(i\) nájdeme v zozname pre vrchol \(a_i\) všetky diery \(j\) vo vzdialenosti najviac \(b_i - w_j\) a vyberieme z nich dieru s najlepšiou cenou.

Celková časová zložitosť tohoto riešenia bude \(O((n+q)\cdot m)\), čo stačilo na získanie 4 bodov.

Strom je plytký!

V tretej sade má strom hĺbku najviac \(100\). Skúsme sa zamyslieť, ako nám to pomôže pri riešení úlohy.

Zoberme si \(i\)-tu query a predstavme si, že by sme na ňu použili dieru \(j\). Potom cesta z diery do \(a_i\) musí prejsť nejakým predkom \(a_i\) (každý vrchol je sám sebe predkom). Zoberme si tak každého predka \(a_i\) a diery ktoré sú v jeho podstrome. Všimnime si, že pre každú z týchto dier vieme vypočítať hodnotu “koľko času by nám trvalo sa dostať do \(a_i\) pomocou diery \(j\) ak by sme išli cez predka \(u\)” ako súčet \(w_i+(\text{dĺžka cesty z }u_i\text{ do diery }j) + (\text{dĺžka cesty z }u_i\text{ do }a_i)\). Počítanie týchto hodnôt samo o sebe nie je dobrý nápad, lebo to je pomalé, ale uvidíme, že to povedie k lepšiemu riešeniu.

Túto hodnotu vieme vypočítať ako súčet dvoch hodnôt, jedna závisí od diery \(j\) a \(u\), druhá od \(a_i\) a \(u\), vidíme, že voľba \(j\) ovplyvní len prvú hodnotu a voľba \(i\) len druhu, teda ich môžme spočítať pre všetky \(j\) a \(u\) zvlášť a pre všetky \(i\) a \(u\) zvlášť. Toto počítanie už nebude pomalé, lebo každý vrchol má najviac \(100\) predkov, teda sa vyskytne v \(100\) výpočtoch.

Pre každý vrchol spočítame jeho vzdialenosť od dier v jeho podstrome. Ak by sme mali túto informáciu spočítanú, ľahko nájdeme odpoveď na otázku: ak sme vo vrchole \(u\) a máme ešte \(t\) času, aká je najlacnejšia diera v podstrome vrcholu \(u\), do ktorej sa vieme za čas \(t\) dostať?

Ukážeme si ako:

V každom vrchole \(u\) si budeme pamatať všetky diery v jeho podstrome, ale namiesto ich hodnoty \(w\) k nej ešte pripočítame vzdialenosť do vrcholu \(v\) – vrchol kde sa diera nachádza. Tieto hodnoty označíme \(w'\). Teraz platí:

Ak sa pýtame na otázku pre vrchol \(u\) a čas \(t\), vyberieme tie diery, ktoré majú \(w' \leq t\) a na tie sa budeme vedieť dostať. (Ak hovorím, že sa na ne vieme dostať, myslím že sa vieme z vrcholu \(0\) premiestniť do nich a potom peši prejsť do \(u\), to celé v čase najviac \(t\).)

Teraz si diery vo vrchole \(u\) usporiadame podľa hodnoty \(w'\). Potom nás zaujíma len prvých niekoľko dier s dosť malou \(w'\). Z nich vieme vybrať tú s najlepšou cenou napríklad pomocou prefixových miním, keďže sa vždy pýtame na prefix a hodnoty sa nemenia.

Ak sa teraz budeme pýtať postupne na predkov vrcholu \(a_i\), pričom vhodne upravíme čas, ktorý nám ešte zostáva, a hľadať pomocou tejto otázky najlepšie diery, dostaneme sa zjavne k riešeniu.

Celé predpočitanie teda bude vyzerať takto:

  1. Každú dieru \(i\) zaznačíme aj do jej predkov, pričom k \(w_i\) pripočítame vždy dĺžku cesty do toho konkrétneho predka, tým získame hodnoty \(w'\).
  2. Pre každý vrchol diery usporiadame podľa \(w'\).
  3. Pre každý vrchol spočítame prefixové minimá podľa hodnôt \(c\).

Každú dieru zaznačujeme do jej predkov a potom týchto \(O(mH)\) záznamov utriedime, teda dostávame zložitosť \(O(mH \log m)\).

Odpoveď na otázku: “som vo vrchole \(u\) a mám ešte \(t\) času” potom získame tak, že v zozname pre vrchol \(u\) binárne vyhľadáme poslednú dieru, ktorú vieme použiť a následne sa spýtame na prefixové minimum.

Celé riešenie jednej query teda bude:

  1. Začíname vo vrchole \(u=a_i\) s časom \(t=b_i\).
  2. Spýtame sa na otázku “som vo vrchole \(u\) a mám \(t\) času” a upravíme výsledok.
  3. Ak nie sme v koreni stromu priradíme \(t=t-\)čas na prejdenie do otca u, \(u=\) otec u. Ideme znova na krok 2.
  4. Zohľadnili sme všetky možnosti, teda vieme výsledok.

Pre každú query H krát vyhľadáme odpoveď, čo dáva zložitosť \(O(qH \log m)\).

Celé riešenie má časovú zložitosť \(O(n + mH \log m + qH \log m)\). Pamäťová zložitosť bude \(O(mH + n)\).

Na čo nám to bolo?

Prečo sme mali dlhočizný vzorák o nejakom riešení, ktoré ani neprešlo na plný počet bodov? Odpoveď znie, že často sú podúlohy nastavené tak, aby pomohli k riešeniu celej úlohy. A táto úloha nie je výnimkou.

Nechcem spoilovať, tak tento nadpis nenapíšem

Kebyže máme strom plytký, úlohu ľahko vyriešime. Všeobecne, ak je strom hlboký a chceme, aby bol plytký, správnym nástrojom sú centroidy. Ak ste nikdy nepočuli o centroidoch a centroidovej dekompozícií, môžete si o tom prečítať tu.

V rýchlosti sa to da opisať takto:
Centroidovou dekompozíciou vhodne usporiadame vrcholy stromu tak, že sa úplne nezachová samotná štruktúra zadaného stromu, ale vznikne nový, úplne iný strom hĺbky najviac \(\log n\) - čo je dobré znamenie, lebo pre takto hlboké stromy už poznáme riešenie.

Tento strom však bude mať jednu peknú vlastnosť. Keď sa pozrieme na jeho ľubovolný vrchol v centroidovom a pôvodnom strome, a pozrieme sa na podgrafy, ktoré vzniknú keď ho odstránime, budú mať tieto podgrafy rovnaké vrcholy pre centroidový aj pôvodný strom.

Toto sa ukáže ako veľmi užitočná vlastnosť, ak sa pýtame na cesty v strome, lebo pre vrchol na ceste v pôvodnom aj centroidovom strome platí, že ak ho odstránime, bude začiatočný a koncový vrchol cesty v rôznych podstromoch – z formulácie vidíme, že je práve to čo centroidové stromy poskytujú.

Keď si teraz porovnáme, čo sme robili v predošlom odseku za 6 bodov, jediná podstatná vlastnosť, ktorú sme potrebovali, bola, že aspoň v jednom vrchole, ktorý je na ceste medzi nejakou dierou a query, zohľadníme túto dieru. Stále je to tá istá vlastnosť, čo som prakticky napísal 3x za sebou, aby to bolo vidieť, a čo sa v centroidových stromoch zachováva. (toto celé ešte nižšie dokážeme)

Otázka znie, či si aj pre takýto strom budeme vedieť predpočítať podobné hodnoty ako minule. Bystrému čitateľovi hneď dojde, že to je len rečnícka otázka, a že to ide :p

Začneme rovnako ako predtým, každú dieru zaznačíme aj do jej predkov v centroidovom strome. Problém bude, že novú hodnotu \(w'\) diery nebudeme tak ľahko vedieť spočítať. Nebudeme sa môcť vždy iba pozrieť na cenu hrany do otca a túto cenu pripočítať. Na chvíľu ale predpokladajme že máme funkciu \(\textit{tree}\_\textit{dist}(a, b)\), ktorá vráti vzdialenosť vrcholov \(a\) a \(b\) v strome zo vstupu.

Pomocou tejto funkcie už ľahko dokončíme predpočítanie tak ako sme to robili minule, s výnimkou, že hodnota, ktorú si uložíme vo vrchole \(u\), ak sme pridali dieru do vrcholu \(v\) bude \(w + \textit{tree}\_\textit{dist}(u, v)\).

Ak by sme aj druhú časť riešenia upravili dostávame to isté riešenie, len s drobnými zmenami:

  1. Prvý krok je rovnaký.
  2. Spýtame sa otázku na vrchol \(u\) s časom \(b_i - \textit{tree}\_\textit{dist}(a_i, u)\) – uvedomme si, že presne toto robíme aj v predošlej verzií.
  3. Nastavíme \(u\) na jeho otca v centroidovom strome.

Vidíme, že sa naozaj oplatilo robiť celé to predošlé riešenie, keďže toto nie je o moc iné – teda samozrejme za predpokladu, že to čo sme tu teraz napísali a (vyššie som povedal, že to platí) naozaj platí.

Ukážeme, že to naozaj funguje a implementácia

Môžeme si všimnúť, že v tomto riešení sa nám dosť často stane, že keď v nejakom vrchole \(v\) zohľadňujeme nejakú dieru \(d\), museli by sme, kebyže si to nakreslíme v pôvodnom strome, viackrát prejsť po tej istej hrane/ceste. (formálne vrchol \(v\) je predok \(lca(v, d)\)) Teda hodnota \(w'\) bude v takýchto prípadoch moc veľká. Nikdy sa nám našťastie ale nestane, že by sme mali pre nejakú dieru hodnotu \(w'\) moc malú, keďže vždy pripočítame \(\textit{tree}\_\textit{dist}\).

Teda určite nájdeme výsledok aspoň tak veľký ako má byť. To je fajn. Teraz nám stačí ukázať, že aspoň pri jednom vrchole \(v\), ktorý budeme pri query kontrolovať budeme mať cestu do diery \(d\), kde ani jednu hranu nepoužijeme viac krát. Inými slovami, že nájdeme výsledok taký malý, resp. práve taký, aký má byť.

Nie je ťažké si uvedomiť, že správne vzdialenosti bez opakovaných hrán dostaneme práve pre vrcholy \(v\), ktoré sú v centroidovom strome predkami \(d\) aj \(a_i\) (alebo sú to \(d\) alebo \(a_i\)) a pre ktoré \(a_i\) a \(d\) ležia v rozdielných centroidových podstromoch, a teda aj v rozdielných podstromoch v pôvodnom strome. Chceme ukázať, že existuje aspoň jeden vrchol, ktorý spĺňa túto vlastnosť. Na to aby sme to ukázali, zíde sa nám vedieť ako centroidový strom vytvárame – z tohoto postupu to už priamo vyplýva.

Centroidová dekompozícia

Pre nejaký strom vieme nájsť centroid jedným prehľadávaním. Ak pre vrchol platí, že veľkosti podstromov vo všetkých jeho susedoch je \(\leq\) polovici vrcholov v strome, je tento vrchol centroid. Inak je centroid v podstrome, ktorý má najväčšiu veľkosť a na ten sa rekurzívne zavoláme. Každý strom má centroid a týmto postupom ho nájdeme. (Dôkaz tohoto algoritmu neuvádzame.)

Keď sme našli centroid, musíme nájsť centroidy v podstromoch jeho synov a na to rekurzívne opäť použijeme vyššie popísaný algoritmus.

Pauza na pitie.

Pokračujme v dôkaze. Pozrime sa na vrcholy na ceste medzi \(a_i\) a \(d\). Ak za centroid zvolíme ľubovoľný iný vrchol a graf rozdelíme na jeho podstromy, celá táto cesta bude stále v jednom podstrome. Čiže z hľadiska cesty sa nič zaujímavé nestalo.

A ak vyberieme za centroid jeden z vrcholov na ceste, cesta sa rozdelí do jeho podstromov, a to tak, že vrchol \(a_i\) bude v podstrome jedného jeho syna a vrchol s dierou \(d\) bude v nejakom inom. Teda minimálne prvý vrchol z cesty, ktorý v algoritme vyššie vyberieme za centroid bude spĺňať požadovanú vlastnosť, a teda pri ňom dostaneme správne vzdialenosti od \(a_i\) aj \(d\).

Teraz vieme, že máme správne riešenie, stačí nám implementovať posledný detail.

Funkcia \(\textit{tree}\_\textit{dist}\)

Na implementáciu tejto funkcie vieme napríklad použiť binary lifting, alebo teda klasický LCA algoritmus. Ak ste o tom ešte nikdy nepočuli, môžete si viac prečítať v tomto článku, kvôli dĺžke vzoráku to tu už neuvádzame.

Ak sa nám ale nechce kódiť binary lifting, ide to aj krajšie! Celkovú časovú zložitosť to síce nezlepší, ale v praxi to program môže niekoľkonásobne zrýchliť.

Môžme si uvedomiť, že vždy sa pýtame len na vzdialenosti medzi vrcholom a nejakým jeho centroidovým predkom. Tých je však len \(O(\log n)\) preto môžeme mať zapamätanú pre každý vrchol vzdialenosť do jeho centroidových predkov. Jeden spôsob ako takúto informáciu získať, je priamo pri dekompozícií si pre novonájdený centroid spočítať vzdialenosť do všetkých vrcholov v jeho podstrome. Zložitosť na predpočítanie zostane \(O(n \log n)\), ale na query sa zmenšila na \(O(1)\), lebo sa stačí len hodnoty pamätať v poli. Detaily implementácie prenecháme na čitateľovi.

Časová a pamäťová zložitosť

Centroidovú dekompozíciu zvládneme v čase \(O(n \log n)\), rovnako rýchlo bude trvať aj predpočítanie vzdialeností do centroidových predkov.

Predpočítanie dier nám zaberie \(O(m \log m \log n)\) času – najskôr diery zapisujeme do predkov, čo trvá \(O(m \log n)\), teda to zanedbáme, potom to celé utriedime a spravíme prefixové súčty – to je výsledná zložitosť.

Samotné odpovede na queries budú trvať \(O(q \log n \log m)\) – pozrieme \(O(\log n)\) predkov a binárne vyhľadáme, ktoré diery sú použiteľné.

Celá časová zložitosť bude \(O(m\log m \log n + q \log n \log m + n \log n)\).

Pamäťová bude \(O(n \log n + m \log n)\), lebo si pamätáme vzdialenosti z vrcholov do centroidových predkov a každú dieru v jej centroidových predkoch.

Postup, ktorý sme si tu ukázali má tú výhodu, že je online – teda otázky spracuváva postupne, každú dostatočne rýchlo. Na precvičenie môžeš skúsiť vymyslieť riešenie na rovnakú úlohu s tým, že vrámci query môže pribudnúť nová diera. Hint – stačí len vhodne upraviť toto riešenie.

#include <bits/stdc++.h>

using namespace std;

#define inf 1e18

vector<vector<pair<int, int>>> g; // graph. Only storing children, not parents
vector<int> subtree_sizes;        // subtree sizes
vector<int> p, w;                 // input arrays

// centroid decomposition
int css(int v)
{ // dfs to compute subtree sizes
    subtree_sizes[v] = 1;
    for (auto [i, j] : g[v])
    {
        subtree_sizes[v] += css(i);
    }
    return subtree_sizes[v];
}

vector<int> centroid_parent;                // centroid parents
vector<vector<long long>> dist_cent_parent; // distances to centroid parents. Max n log n size

void compute_distances(int my_cent, int root)
{ // distances to nodes from centroid my_cent
    queue<pair<int, long long>> f;
    f.push({my_cent, 0});
    unordered_map<int, bool> bol;
    
    while (!f.empty())
    { // compute distances with bfs
        auto [v, t] = f.front();
        f.pop();
        if (bol[v] || centroid_parent[v] != -2)
            continue; // already visited or in another centroid subtree

        bol[v] = true;
        dist_cent_parent[v].push_back(t);

        for (auto s : g[v])
        {
            f.push({s.first, s.second + t});
        }
        if (v != root)
        { // do not go to another centroid subtrees
            f.push({p[v], t + w[v]}); // edges to parent are sotred independently
        }
    }
}

void decompose(int v, int size, int parent)
{ // decompose current subtree to centroids
    if (centroid_parent[v] != -2)
        return; // already done

    int my_cent = v;
    while (true)
    { // find centroid with bfs
        bool ok = true;
        int m = 0;
        for(int i = 0; i < g[my_cent].size(); i++)
        {
            if (subtree_sizes[g[my_cent][i].first] > size / 2)
                ok = false; // not a centroid
            if (subtree_sizes[g[my_cent][i].first] > subtree_sizes[g[my_cent][m].first])
                m = i; // find biggest subtree
        }
        if (ok)
            break; //is centroid
        my_cent = g[my_cent][m].first; // move to biggest subtree
    }
    compute_distances(my_cent, v);
    int t = my_cent;
    while (t != v && t != -1 && centroid_parent[t] == -2)
    { // recompute subtree sizes in new subtree of v
        t = p[t];
        subtree_sizes[t] -= subtree_sizes[my_cent];
    }
    subtree_sizes[my_cent] = 0;
    centroid_parent[my_cent] = parent;
    if (my_cent != v)
        decompose(v, subtree_sizes[v], my_cent); // one subtree is rooted in v
    for (auto [i, j] : g[my_cent])
        decompose(i, subtree_sizes[i], my_cent); // other are rooted in children of my_cent
}
//end of centroid decomposition

vector<vector<pair<long long, long long>>> holes_distance; // for each vertex: holes from centroid subtree with distance to vertex
void add_hole(int v, int c, long long t)
{ // add hole to all centroid parents
    int akt = v;
    int j = 0; // number of jumps upwards
    while (akt != -1)
    {
        holes_distance[akt].push_back({t + dist_cent_parent[v][j], c});
        akt = centroid_parent[akt];
        j++;
    }
}

void solve()
{
    int n; cin >> n;
    //clear global arrays after each testcase
    p.clear(); p.resize(n, -1);
    w.clear(); w.resize(n, -1);
    g.clear(); g.resize(n);
    subtree_sizes.clear(); subtree_sizes.resize(n, 0);
    centroid_parent.clear(); centroid_parent.resize(n, -2);
    holes_distance.clear(); holes_distance.resize(n, {make_pair(-inf, inf)}); // add always reachable hole with infinite cost
    dist_cent_parent.clear(); dist_cent_parent.resize(n);

    for(int i = 1; i < n; i++) cin >> p[i];
    for(int i = 1; i < n; i++) cin >> w[i];
    for(int i = 1; i < n; i++)
    {
        int a = i, b = p[i], c = w[i];
        g[b].push_back({a, c}); // only edges to children
    }
    css(0);
    decompose(0, subtree_sizes[0], -1);
    for(int i = 0; i < n; i++) reverse(begin(dist_cent_parent[i]), end(dist_cent_parent[i])); // distances were computed in the other order
    // decomposition with precomputed distances finished

    int m;
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int v, c, t;
        cin >> v >> c >> t;
        add_hole(v, c, t);
    }
    add_hole(0, 0, 0); // equivalent to not using a hole

    for(int i = 0; i < holes_distance.size(); i++) // sort and compute prefix maximums
    {
        sort(begin(holes_distance[i]), end(holes_distance[i]));
        for(int j = 1; j < holes_distance[i].size(); j++)
            holes_distance[i][j].second = min(holes_distance[i][j - 1].second, holes_distance[i][j].second); // prefix maximums
    }
    // precomputing distances to holes from centroid parents done

    int q;
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        int v, mt;
        cin >> v >> mt;
        long long ans = inf;
        int t = v;
        int j = 0; // number of jumps upwards
        while (t != -1)
        {
            long long curr_time = mt - dist_cent_parent[v][j];
            auto akt = upper_bound(begin(holes_distance[t]), end(holes_distance[t]),
                                   make_pair(curr_time, (long long)inf));
            akt--; // find the last reachable hole
            ans = min(ans, akt->second);
            t = centroid_parent[t];
            j++;
        }
        if (ans == inf)
            ans = -1;
        cout << ans << "\n";
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.