Arborele din exemplu arată astfel:

!problema/lca?arbore.gif 70%!

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

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;}.