Fişierul intrare/ieşire:lca.in, lca.outSursăInfoarena
AutorTeorieAdăugată detudorcomanTudor Coman tudorcoman
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inlca.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 sa te autentifici pentru a trimite solutii. Click aici