Fișierul intrare/ieșire lca.in, lca.out Sursă Infoarena
Autor teorie Adăugată de avatar tudorcoman Tudor Coman tudorcoman
Timp de execuție pe test 2.75 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty

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

Trebuie să te autentifici pentru a trimite soluții. Click aici