Fișierul intrare/ieșire | lca.in, lca.out | Sursă | Infoarena |
---|---|---|---|
Autor | teorie | Adăugată de | Tudor Coman • tudorcoman |
Timp de execuție pe test | 2.75 sec | Limită de memorie | 65536 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Lowest Common Ancestor
Se dă un arbore cu rădăcină T. Cel mai apropiat strămoș comun a două noduri u și v este nodul w care este strămoș al ambelor noduri u și v și are cea mai mare adâncime în T.
Considerăm că arborele T are n noduri și are rădăcina în nodul 1. Dându-se o mulțime arbitrară P = {{u,v}}, cu m perechi neordonate de noduri din T, se cere să se determine cel mai apropiat strămoș al fiecărei perechi din P.
Date de intrare
Pe prima linie a fișierului de intrare lca.in se găsesc n și m. Următoarea linie conține n-1 numere naturale, cel de-al i-lea număr reprezentând tatăl nodului i+1 (nodul 1 fiind rădăcină nu are tată). Pe următoarele m linii se află câte o pereche de numere naturale, reprezentând elementele mulțimii P.
Date de ieșire
Fișierul de ieșire lca.out va conține m linii, linia a i-a conținând răspunsul celei de a i-a întrebări.
Restricții
- 1 ≤ n ≤ 100 000
- 1 ≤ m ≤ 2 000 000
Exemplu
lca.in | lca.out |
---|---|
11 5 1 1 2 2 2 4 4 6 3 3 10 11 8 9 5 11 5 6 4 2 |
3 2 1 2 2 |