== 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 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$".

h2. Date de intrare

O 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ă ... puncte, iar sursa care se bazează pe această idee este 'aceasta':...

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: $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:

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$ |