Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-11-24 14:21:59.
Revizia anterioară Revizia următoare
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
- 2 ≤ N ≤ 100.000
- 1 ≤ M ≤ 2.000.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici
