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.

*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.
*UPDATE* Când vrei să afli LCA-ul pentru 2 noduri, mai întâi, aduci ambele noduri pe acelaşi nivel (nivelul minim al celor două), iar apoi cauţi să mergi cu 2^k^ nivele mai sus cu ambele noduri doar dacă nodurile cu 2^k^ nivele mai sus pentru ambele noduri sunt diferite. Astfel, se garantează că LCA-ul celor două noduri va fi cu un nivel mai sus decât nivelul la care am ajuns cu cele două noduri. Soluţia o găseşti şi în articolul de pe TopCoder.

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

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:

* '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") ==