Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | lca.in, lca.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Cella Florescu •cella.florescu |
| Timp execuţie pe test | 1.4 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Lowest Common Ancestor
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".
Date de intrare
Pe prima linie a fişierului de intrare lca.in se află N şi M. Pe următoarea linie se află N - 1 numere naturale, cel de-al i-lea număr reprezentând tată nodului i + 1 (nodul 1 fiind rădăcină nu are tată). Pe următoarele M linii se află câte 2 numere naturale, reprezentând numerele de ordine ale nodurilor care definesc întrebările.
Date de ieşire
Fişierul de ieşire lca.out va conţine M linii, linia i conţinând răspunsul la întrebarea i.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 2.000.000
- Pentru 20% din teste 1 ≤ N, M ≤ 1.000
Exemplu
| lca.in | lca.out |
|---|---|
| 11 5 1 1 2 2 2 4 4 6 3 3 10 11 8 9 5 11 5 6 4 2 | 3 2 1 2 2 |
Explicaţie
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 
ar trebui să obţină 30 puncte şi se găseşte aici
O altă soluţie descrisă în acest articol având complexitatea finală de 
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. Se reţine pentru fiecare nod, strămoşul cu 
nivele mai sus, unde k ia valori între 
şi 
. 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 
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:
| reprezentarea Euler | 1 | 2 | 4 | 7 | 4 | 8 | 4 | 2 | 5 | 2 | 6 | 9 | 6 | 2 | 1 | 3 | 10 | 3 | 11 | 3 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| nivelul | 0 | 1 | 2 | 3 | 2 | 3 | 2 | 1 | 2 | 1 | 2 | 3 | 2 | 1 | 0 | 1 | 2 | 1 | 2 | 1 | 0 |
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 
, soluţie care ar trebui sa obţină 70 de puncte, sursa care se bazează pe acest principiu fiind aceasta.
Mai eficient, pentru determinarea minimului unei subsecvenţe se poate folosi RMQ. Astfel, complexitatea finală va fi 
, aceasta soluţie obţinând 100 de puncte, sursa care se bazează pe această idee se găseşte aici.
