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

• 1 ≤ n ≤ 100 000
• 1 ≤ m ≤ 2 000 000

Exemplu