h2. Restricţii

* $2 ≤ N ≤ 100.000$

* $1 ≤ N ≤ 100.000$

* $1 ≤ M ≤ 2.000.000$

* Pentru $20%$ din teste $1 ≤ N, M ≤ 1.000$

h2. Exemplu

!problema/lca?arbore.gif 80%!

O primă soluţie, care caută între toate nodurile arborelui şi îl reţine pe cel care strămoş al ambelor noduri din întrebare, având complexitatea fi nală <tex>O(N*M)</tex> ar trebui să obţină ... puncte şi se găseşte 'aici':...
 
O altă soluţie descrisă în 'acest articol':multe-smenuri-de-programare-in-cc-si-nu-numai având complexitatea finală de <tex>O(N + M\sqrt{N})</tex> ar trebui să obţină ... puncte. 'Aici':... se găseşte o sursă care se bazează pe această idee.
 
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. 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 maxim 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:
$1 2 4 7 4 8 4 2 5 2 6 9 6 2 1 3 10 3 11 3 1$
 
De exemplu, pentru nodurile $8$ şi $9$, răspunsul este nodul cu nivel maxim din secvenţa $8 4 2 5 2 6 9$, mai exact nodul 2.
 

== include(page="template/taskfooter" task_id="lca") ==