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

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: