* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 2.000.000$

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

h2. Exemplu

h3. Explicaţie

!problema/lca?arbore.gif 80%!

Arborele din exemplu arată astfel:
 
!problema/lca?arbore.gif 100%!

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 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 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ă 60 puncte. 'Aici':job_detail/368625?action=view-source se găseşte o sursă care se bazează pe această idee. Deşi nu este cea mai eficientă, avantajul acestei soluţii constă în faptul că se implementează foarte repede.

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ă $60$ puncte, iar sursa care se bazează pe această idee este 'aceasta':job_detail/368488?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, 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ă $60$ puncte, iar sursa care se bazează pe această idee este 'aceasta':job_detail/368639?action=view-source

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:

Pentru a implementa această soluţie, se folososesc 'arbori de intervale':problema/arbint, având complexitatea <tex>O(N + Mlog_{2}N)</tex>, soluţie care ar trebui sa obţină 70 de puncte, sursa care se bazează pe acest principiu fiind 'aceasta':job_detail/368434?action=view-source.
Mai eficient, pentru determinarea minimului unei subsecvenţe se poate folosi 'RMQ':problema/rmq. Astfel, complexitatea finală va fi <tex>O(Nlog_{2}N + M)</tex>, aceasta soluţie obţinând $100$ de puncte, sursa care se bazează pe această idee se găseşte 'aici':job_detail/368469?action=view-source.

Un articol care explică foarte bine atât RMQ, cât şi LCA se găseşte pe 'TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
 

h3. Aplicaţii
* 'CT':problema/ct