== include(page="template/taskheader" task_id="lca") ==

Se dă un 'arbore':http://en.wikipedia.org/wiki/Tree_%28graph_theory%29 cu $N$ noduri, având rădăcina în nodul $1$. Să se răspundă la $M$ întrebări de forma: "Care este 'cel mai apropiat strămoş comun':http://en.wikipedia.org/wiki/Lowest_common_ancestor al nodurilor $x$ şi $y$".

Se dă un 'arbore':http://en.wikipedia.org/wiki/Tree_%28graph_theory%29 cu rădăcină $T$. 'Cel mai apropiat strămoş comun':http://en.wikipedia.org/wiki/Lowest_common_ancestor 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$.

h2. 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 $2$ numere naturale, reprezentând nodurilor care definesc întrebările.

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$.

h2. Date de ieşire

Fişierul de ieşire $lca.out$ va conţine $M$ linii, linia $i$ conţinând răspunsul la întrebarea $i$.

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.

h2. Restricţii

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 2 000 000$

* $1 ≤ n ≤ 100 000$
* $1 ≤ m ≤ 2 000 000$

h2. Exemplu

2
|

!> problema/lca?arbore.gif 50%!
 

h3. Explicaţie

Arborele din exemplu arată astfel:

Arborele din exemplu arată ca în figura alăturată...

!< problema/lca?arbore.gif 70%!

h2. Indicaţii de rezolvare

O primă soluţie, care caută LCA-ul celor două noduri mergând "în sus" pe ramurile nodurilor până când acestea se intersectează, având complexitatea de <tex>O(N*M)</tex>, ar trebui să obţină $30$ puncte şi se găseşte 'aici':job_detail/368458?action=view-source.

O primă 'soluţie':job_detail/368458?action=view-source, care caută LCA-ul celor două noduri mergând "în sus" pe ramurile nodurilor până când acestea se intersectează, având complexitatea de <tex>O(N*M)</tex>, ar trebui să obţină $30$ puncte.

O altă soluţie descrisă în 'acest articol':multe-smenuri-de-programare-in-cc-si-nu-numai, având complexitatea finală de <tex>O(N + M\sqrt{N})</tex>, ar trebui să obţină 60 puncte. 'Aici':job_detail/368625?action=view-source se găseşte o sursă care se bazează pe această idee. Deşi nu este cea mai eficientă, avantajul acestei soluţii constă în faptul că se implementează foarte repede.

O altă 'soluţie':job_detail/368625?action=view-source descrisă în 'acest articol':multe-smenuri-de-programare-in-cc-si-nu-numai, având complexitatea finală de <tex>O(N + M\sqrt{N})</tex>, ar trebui să obţină 60 puncte. Deşi nu este cea mai eficientă, avantajul acestei soluţii constă în faptul că se implementează foarte repede.

O altă soluţie relativ uşor şi rapid de implementat în condiţii de concurs este cea care foloseşte ideea de la problema 'Strămoşi':problema/stramosi. Se reţine pentru fiecare nod strămoşul cu <tex>2^{k}</tex> nivele mai sus, unde $k$ ia valori între <tex>1</tex> şi <tex>log_{2}N</tex>. Astfel, pentru fiecare query, se aduce nodul de pe nivelul mai mare pe acelaşi nivel cu celălalt, după care se poate afla în timp logaritmic $LCA$-ul celor două noduri. Complexitatea finală este <tex>O(Nlog_{2}N + Mlog_{2}N)</tex>. Această soluţie ar trebui să obţină $60$ puncte, iar sursa care se bazează pe această idee este 'aceasta':job_detail/368667?action=view-source.

O altă soluţie relativ uşor şi rapid de implementat în condiţii de concurs este cea care foloseşte ideea de la problema 'Strămoşi':problema/stramosi. Se reţine pentru fiecare nod strămoşul cu <tex>2^{k}</tex> nivele mai sus, unde $k$ ia valori între <tex>1</tex> şi <tex>log_{2}N</tex>. Astfel, pentru fiecare query, se aduce nodul de pe nivelul mai mare pe acelaşi nivel cu celălalt în timp logaritmic, după care, tot în timp logaritmic, se poate afla $LCA$-ul celor două noduri. Complexitatea finală este deci <tex>O(Nlog_{2}N + Mlog_{2}N)</tex>. Această 'soluţie':job_detail/369283?action=view-source ar trebui să obţină $70$ puncte.

*TODO* Nu înţeleg exact soluţia de mai sus. Eu ştiu de O(N logN + M log^2^N), pentru că o dată cauţi binar rezultatul şi a doua oară mergi cu informaţiile reţinute în sus în logN.

O 'soluţie':job_detail/369478?action=view-source ce se foloseşte de 'algoritmul lui Tarjan':http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm care rezolvă query-urile offline, bazându-se pe structura de date 'mulţimi disjuncte':problema/disjoint. Aceasta are complexitatea de <tex>O(Nlog*N + M)</tex> şi ar trebui să obţină $70$ de puncte din cauza numărului mare de query-uri. Asemenea metodei cu RMQ prezentată mai jos, şi această metodă foloseşte o cantitate mai mare de memorie, <tex>O(M)</tex> care în anumite condiţii nu se încadrează limitei de memorie. Un alt dezavantaj în anumite cazuri este faptul că query-urile nu se parcurg în ordine, ci se rezolvă offline, adică este necesară cunoaşterea lor în prealabil.

Soluţia care ar trebui să obţină $100$ de puncte se bazează pe următoarea observaţie: „Cel mai apropiat strămoş comun a $2$ noduri este nodul de nivel minim dintre primele apariţii ale nodurilor din query din 'reprezentarea Euler a arborelui':lowest-common-ancestor.” În cazul de faţă, reprezentarea Euler a arborelui este următoarea, pe următorul rând găsindu-se nivelurile nodurilor:

|_. $Reprezentarea Euler$| $1$ | $2$ | $4$ | $7$ | $4$ | $8$ | $4$ | $2$ | $5$ | $2$ | $6$ | $9$ | $6$ | $2$ | $1$ | $3$ | $10$ | $3$ | $11$ | $3$ | $1$ |
|_. $Nivelul$ | $0$ | $1$ | $2$ | $3$ | $2$ | $3$ | $2$ | $1$ | $2$ | $1$ | $2$ | $3$ | $2$ | $1$ | $0$ | $1$ | $2$ | $1$ | $2$ | $1$ | $0$ |

Pentru exemplificare, nodurile $8$ şi $9$ au cel mai apropiat strămoş comun nodul cu nivel minim din secvenţa $8 4 2 5 2 6 9$, adică nodul $2$, care are nivelul $1$.

Pentru exemplificare, nodurile $8$ şi $9$ au cel mai apropiat strămoş comun nodul cu nivel minim din secvenţa $8 4 2 5 2 6 9$, adică nodul $2$, care are nivelul $1$. Pentru a implementa această soluţie, putem folosi 'arbori de intervale':problema/arbint, având complexitatea <tex>O(N + Mlog_{2}N)</tex>, 'soluţie':job_detail/368434?action=view-source care ar trebui să obţină $70$ de puncte. Mai eficient, ţinând cont de restricţiile problemei, pentru determinarea minimului unei subsecvenţe se poate folosi 'RMQ':problema/rmq. Astfel, complexitatea finală va fi <tex>O(Nlog_{2}N + M)</tex>, această 'soluţie':job_detail/368469?action=view-source obţinând $100$ de puncte. Dezavantajul acestei metode constă în faptul că se foloseşte <tex>O(Nlog_{2}N)</tex> memorie, ceea ce poate fi un impediment în anumite cazuri.

Pentru a implementa această soluţie, se folosesc 'arbori de intervale':problema/arbint, având complexitatea <tex>O(N + Mlog_{2}N)</tex>, 'soluţie':job_detail/368434?action=view-source care ar trebui sa obţină $70$ de puncte. Mai eficient, ţinând cont de restricţiile problemei, pentru determinarea minimului unei subsecvenţe se poate folosi 'RMQ':problema/rmq. Astfel, complexitatea finală va fi <tex>O(Nlog_{2}N + M)</tex>, această 'soluţie':job_detail/368469?action=view-source obţinând $100$ de puncte.

Un articol ce explică foarte bine atât RMQ, cât şi LCA se găseşte pe 'TopCoder':https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/.

Un articol ce explică foarte bine atât RMQ, cât şi LCA se găseşte pe 'TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor.
 
h3. Aplicaţii

h2. Aplicaţii

* 'CT':problema/ct
* 'Atac':problema/atac

* 'Pirati':problema/pirati

* 'Concurs':problema/concurs

* 'Query on a tree I':https://www.spoj.pl/problems/QTREE/
* 'Query on a tree II':https://www.spoj.pl/problems/QTREE2/
 

* 'Delay':problema/delay
* 'Radiatie':problema/radiatie
* 'Ratina':problema/ratina
* 'Query on a tree I':https://www.spoj.pl/problems/QTREE/, spoj
* 'Query on a tree II':https://www.spoj.pl/problems/QTREE2/, spoj

== include(page="template/taskfooter" task_id="lca") ==

4319