Revizia anterioară Revizia următoare
| 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 | 0.9 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate | N/A |
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
- ... ≤ ... ≤ ...
Exemplu
| lca.in | lca.out |
|---|---|
| This is some text written on multiple lines. |
This is another text written on multiple lines. |
Explicație
...
