== 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* Am înţeles. Dar din câte văd tu le aduci pe acelaşi nivel în timp liniar. Dacă ai un lanţ atunci nu ai nicio şansă să obţii complexitatea de care zici. Dovadă că în O(NlogN + Mlog^2^N) îmi merge mai repede.
*UPDATE* Exact asta mi se pare dubios, pentru că la mine Lmax este logaritm în baza 2 din înalţimea maximă a arborelui, iar eu am două foruri de la Lmax la $1$. De altfel, testul pe care pică este testul 7, care este defapt un lanţ.

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 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.
 
O altă soluţie este '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. Are complexitatea de <tex>O(Nlog*N + M)</tex> şi ar trebui să obţină $100$ de puncte. O sursă care se bazează pe această idee este 'aceasta':...

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.

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.

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

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