== include(page="template/taskheader" task_id="lca") ==
Se dă un arbore cu $N$ noduri, având rădăcina in nodul $1$. Să se răspundă la $M$ întrebări de forma: "Care este cel mai apropiat strămoş comun 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 află $N$ şi $M$. Pe următoarea linie se află $N - 1$ numere naturale, cel de-al $i$-lea număr reprezentând tată 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 numerele de ordine ale 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$
* Pentru $20%$ din teste $1 ≤ N, M ≤ 1.000$
* $1 ≤ n ≤ 100 000$
* $1 ≤ m ≤ 2 000 000$
h2. Exemplu
2
|
!> problema/lca?arbore.gif 50%!
h3. Explicaţie
!problema/lca?arbore.gif 80%!
Arborele din exemplu arată ca în figura alăturată...
h2. Indicaţii de rezolvare
O primă soluţie, care caută între toate nodurile arborelui şi îl reţine pe cel care strămoş al ambelor noduri din întrebare, având complexitatea fi nală <tex>O(N*M)</tex> ar trebui să obţină $20$ puncte şi se găseşte 'aici':job_detail/368430?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ă ... puncte. 'Aici':... se găseşte o sursă care se bazează pe această idee.
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 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, la început se aduce nodul de pe nivelul mai mare pe acelaşi nivel cu celalt, iar apoi, 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ă ... puncte, iar sursa care se bazează pe această idee este 'aceasta':...
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.
Soluţia care ar trebui să obţină $100$ de puncte se bazează pe următoarea observaţie: $LCA$-ul a $2$ noduri este nodul de nivel minim dintre primele apariţii ale nodurilor din întrebare din reprezentarea Euler a arborelui. în cazul de faţă, reprezentarea Euler a arborelui este următoarea, iar pe următorul rând sunt nivelurile nodurilor:
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:
table{width:700px; text-align:center;}.
|_. $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$ |
|_. $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, 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.
De exemplu, pentru nodurile $8$ şi $9$, răspunsul este nodul cu nivel minim din secvenţa $8 4 2 5 2 6 9$, mai exact nodul 2, care are nivelul $1$.
Pentru a implementa această soluţie, se folososesc 'arbori de intervale':problema/arbint, având complexitatea <tex>O(N + Mlog_{2}N)</tex>, soluţie care ar trebui sa obţină 70 de puncte, sursa care se bazează pe acest principiu fiind 'aceasta':job_detail/368434?action=view-source.
Mai eficient, pentru determinarea minimului unei subsecvenţe se poate folosi 'RMQ':problema/rmq. Astfel, complexitatea finală va fi <tex>O(Nlog_{2}N + M)</tex>, aceasta soluţie obţinând $100$ de puncte, sursa care se bazează pe această idee se găseşte 'aici':job_detail/368425?action=view-source.
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
* '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") ==
