== 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 $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$".
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 $2$ numere naturale, reprezentând nodurilor care definesc întrebările.
h2. Date de ieşire
Arborele din exemplu arată astfel:
!problema/lca?arbore.gif 100%!
!problema/lca?arbore.gif 70%!
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, 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 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 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 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ă $60$ puncte, iar sursa care se bazează pe această idee este 'aceasta':job_detail/368639?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, 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/368639?action=view-source.
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:
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$ |
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/368469?action=view-source.
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$.
Un articol care 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
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':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor.
h3. Aplicaţii
* 'CT':problema/ct
* 'Atac':problema/atac
* '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/
== include(page="template/taskfooter" task_id="lca") ==
