Zadanie

Na motívy filmu Tristo vymyslel Buj počítačovú hru. Ako za chvíľu iste pochopíte, prešla komplikovaným a dlhým vývojom. Jej hlavné herné mechaniky si priblížime nižšie.

V tejto hre hráč ovláda zhruba tristo dážďoviek. Tie žijú vo svojom podzemnom komplexe, ktorý vyzerá ako graf-strom. Vrcholy stromu reprezentujú miesta v podzemnom komplexe, pričom koreň stromu reprezentuje východ z komplexu.

Každá dážďovka v komplexe okupuje nejaký súvislý úsek vrcholov – teda vrcholy, na ktorých sa nachádza niektorý článok dážďovky, tvoria cestu. Koncovým článkom dážďovky budeme hovoriť hlava a chvost.

Úlohou hráča je riadiť evakuáciu dážďoviek von z komplexu. Dážďovky sú pripravené – aj preto je každá dážďovka otočená hlavou smerom ku koreňu stromu. To znamená, že spomedzi všetkých jej článkov je jej hlava ku koreňu najbližšie.

Hra prebieha v ťahoch. V každom ťahu hráč klikne na niektorú dážďovku, a tá sa pohne o toľko smerom ku koreňu, o koľko sa dá. Nevie sa samozrejme pohnúť do vrcholu, ktorý už je obsadený článkom inej dážďovky. Takisto sa dážďovka nevie natiahnuť – dĺžka dážďovky zostane po vykonaní ťahu rovnaká. Ak po vykonaní ťahu hlava dážďovky dosiahne koreň stromu, dážďovka je zachránená a komplex opúšťa.

No a vašou úlohou bude túto hernú mechaniku čo najefektívnejšie implementovať.

Úloha

Dostanete popis podzemného komplexu. Následne dostanete popis niekoľkých hier, ktoré sa všetky odohrávajú v tomto komplexe.

Popis hry pozostáva z rozmiestnenia dážďoviek v ňom, a postupnosti ťahov hráča. Každý ťah určuje jednu dážďovku, na ktorú hráč klikol. Pre každý hráčov ťah zistite, v ktorých vrcholoch sa bude nachádzať hlava a chvost určenej dážďovky po tom, čo sa ťah vykoná.

Formát vstupu

Na prvom riadku vstupu je jedno celé číslo \(n\) – počet vrcholov stromu.

Nasleduje riadok s \(n\) celými číslami \(p_1, p_2, \ldots, p_n\), pričom susedné čísla sú oddelené práve jednou medzerou. Ak \(p_i = 0\), tak vrchol \(i\) je koreňom stromu. V opačnom prípade je otcom vrcholu \(i\) vrchol \(p_i\).

Nasleduje prázdny riadok, a po ňom riadok s jedným celým číslom \(t\) – počet hier. Nasledujú popisy týchto hier.

Popis hry začína prázdnym riadkom. Za ním nasleduje riadok s jedným celým číslom \(m\) – počet dážďoviek. Nasleduje \(m\) riadkov, a v každom z nich sú dve celé čísla oddelené medzerou – čísla vrcholov, v ktorých sa nachádza hlava a chvost dážďovky.

V ďalšom riadku je jedno celé číslo \(q\) – počet ťahov hráča. Nasledovný riadok obsahuje \(q\) celých čísel \(d_1, d_2, \ldots, d_q\), pričom susedné čísla sú oddelené práve jednou medzerou. \(i\)-te z týchto čísel je poradové číslo dážďovky, na ktorú hráč v \(i\)-tom ťahu klikol.

Obmedzenia

  • \(t \leq 1\,000\)
  • Celkový počet vrcholov, celkový počet dážďoviek ani celkový počet ťahov nepresiahne \(100\,000\).
  • Pre každú dážďovku platí, že vrchol, v ktorom sa nachádza hlava je predkom vrcholu, v ktorom sa nachádza chvost.

Formát výstupu

Pre každý ťah vypíšte na samostatný riadok dve čísla \(h\) a \(c\) oddelené jednou medzerou – čísla vrcholov, v ktorých sa nachádzajú hlava a chvost dážďovky po vykonaní ťahu.

Ak dážďovka komplex opustí, vypíšte namiesto toho saved, a v prípade, že sa dážďovka v komplexe už nenachádza, vypíšte illegal.

Príklady

Input:

14
0 1 1 2 2 2 3 3 5 5 7 10 11 11

2

6
1 2
6 6
9 9
10 12
3 8
13 13
11
6 5 4 1 5 6 3 2 4 3 1

3
1 12
7 14
3 8
6
3 2 1 2 3 2

Output:

7 7
3 8
5 10
saved
saved
saved
9 9
saved
saved
saved
illegal
3 8
7 14
saved
7 14
saved
saved

Najprv sa zamyslime nad tým, čím je určený stav hry. Napríklad si môžeme pamätať popis stromu, a pre každú dážďovku všetky vrcholy, v ktorých je niektorý jej článok. Potrebujeme to ale? V skutočnosti nám stačí si pamätať iba vrchol, v ktorom je hlava dážďovky, a pozíciu chvostu. Tým je zvyšok tela jednoznačne určený.

Keď hráč klikne na dážďovku, chceme vedieť efektívne zistiť, kde sa po kliknutí bude nachádzať jej hlava a kde jej chvost. Z pohľadu kliknutej dážďovky nastane jedna z dvoch možností:

  1. Je nad nami nejaká dážďovka, na ktorú cestou hore narazíme. Konkrétne narazíme na takú dážďovku, ktorej hlava vrchol je (nie nutne priamym) predkom nášej hlavy, a spomedzi všetkých takých dážďoviek je najbližšie.

  2. Nie je nad nami žiadna iná dážďovka, a komplex opustíme. To nastane vtedy, keď žiaden predok našej hlavy neobsahuje hlavu inej dážďovky. Tento prípad je jednoduchý, a ďalej sa ním zaoberať nebudeme.

V prvom prípade nás zaujíma, o koľko hore sa posunie naša hlava. O rovnako veľa sa posunie aj náš chvost. Keď už ale poznáme dážďovku, do ktorej narazíme, vieme ľahko zistiť, kde na ňu narazíme – v najnižšom spoločnom predkovi našej hlavy a jej chvostu. Z toho, aká je vzdialenosť našej hlavy od koreňa (hĺbka), a aká je hĺbka “miesta narazenia” vieme ľahko vypočítať, o koľko sa posunieme hore. Nakoniec musíme našu hlavu aj chvost o toľko posunúť hore.

(Povedzme, že sme klikli na zelenú dážďovku. Jej hlava je na \(16\), najbližší predok s hlavou je \(5\) – takže narazime do červenej dážďovky. Jej chvost je na \(13\), a najnižší spoločný predok \(13\) a \(16\) je \(7\) – tu narazíme. Takže sa posunieme hore o \(hlbka_{16} - hlbka_{7} - 1 = 4 - 2 - 1 = 1\).)

Chceme vedieť robiť efektívne tieto tri operácie:

  1. Dostaneme vrchol \(u =\) hlava kliknutej dážďovky. Chceme nájsť jeho najbližšieho predka s hlavou.

  2. Zistíme jeho majiteľa, a nemu prislúchajúci chvostový vrchol \(v\). Hľadáme najbližšieho spoločného predka \(u\) a \(v\), označme ho \(x\).

  3. Dostaneme \(d = hlbka_u - hlbka_x - 1\), a vrchol \(y\) (naša hlava alebo chvost). Hľadáme \(d\)-teho predka \(y\).

Ako spraviť tieto operácie rýchlo

Prvú operáciu vieme vykonať nasledovne: každému vrcholu stromu priradíme čas objavenia (kedy sme ho v prehľadávaní do hĺbky začali spracovávať) a čas opustenia (kedy sme s jeho spracovávaním skončili). Takto každé z čísel \(1, 2, \ldots, 2n\) prislúcha jednému vrcholu – buď ako čas objavenia, alebo ako čas opustenia.

(Zelené číslo uvedené naľavo od vrcholu je jeho čas objavenia, červené číslo uvedené napravo je čas opustenia.)

Keď chceme nájsť najbližšieho hlavového predka vrcholu \(v\), tak v podstate spomedzi všetkých neskôr opustených hlavových vrcholov hľadáme najskorší taký, že sme ho objavili skôr ako \(v\).

V poli dĺžky \(2n\) si na pozícii \(i\) budeme pamätať, či existuje hlavový vrchol s koncovým časom \(i\). Ak áno, tak na tej pozícii bude čas objavenia tohto vrchola. Potom dotaz “zisti najbližšieho hlavového predka vrcholu \(v\)” vieme zodpovedať takto: pozrieme sa na všetky pozície v poli väčšie ako čas opustenia \(v\). Nájdeme najmenšiu pozíciu, na ktorej je hodnota menšia ako čas objavenia \(v\). Táto pozícia zodpovedá času opustenia najbližšieho hlavového predka \(v\).

Prechod celým poľom by mal časovú zložitosť až \(O(n)\), dá sa to ale implementovať efektívne pomocou intervalového stromu v čase \(O(\log{n})\). Samozrejme treba túto dátovú štruktúru udržiavať – vždy, keď sa nejaká hlava presunie, ju vhodne upravíme.

Druhá operácia je štandardný lowest common ancestor.

Tretia operácia: rozdelíme vrcholy stromu do vrstiev podľa ich hĺbky. Na každej vrstve vrcholy usporiadame podľa ich začiatočných časov. Keď hľadáme \(d\)-teho predka vrcholu \(y\), pozrieme sa na vrstvu \(hlbka_y - d\). Vďaka začiatočným časom vieme binárne vyhľadať predka \(y\) – je to posledný vrchol na tej vrstve, ktorý sme začali spracovávať pred \(y\). (Táto operácia je popísaná aj v nedávnom vzorovom riešení 7. úlohy 1. kola 34. ročníka KSP-O.)

Keď takto implementujeme všetky tri operácie, dostaneme riešenie, ktoré vie odsimulovať jedno kliknutie v čase \(O(\log{n})\).

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ť.