!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ă 20 puncte şi se găseşte 'aici':...

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ă $20$ 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.

De exemplu, pentru nodurile $8$ şi $9$, răspunsul este nodul cu nivel minim din secvenţa $8 4 2 5 2 6 9$, mai exact nodul 2, care are nivelul $1$.
Pentru a implementa această soluţie, se folososesc arbori de intervale, având complexitatea <tex>O(N + Mlog_{2}N)</tex>, soluţie care ar trebui sa obţină ... de puncte, sursa care se bazează pe acest principiu fiind 'aceasta':....

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':...

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':...

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