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*Păi când vrei să afli LCA-ul pentru 2 noduri, mai întâi, aduc ambele noduri pe acelaşi nivel (nivelul minim al celor două), iar apoi caut să merg 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.

*UPDATE* Când vrei să afli LCA-ul pentru 2 noduri, mai întâi, aduc ambele noduri pe acelaşi nivel (nivelul minim al celor două), iar apoi caut să merg 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.

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: