h1(#arborest). 'Arborest':problema/arborest

h2. Aceasta pagina trebuie sa ramana private pana la sfarsitul rundei!

Se poate observa usor ca atunci cand modificam tatal unui nod, este cel mai bine sa il modificam in radacina arborelului, $1$. Putem cauta binar adancimea maxima a arborelui. Vrem ca pentru o anumita adancime maxima $q$ sa aflam $nr$ numarul de mutari necesar pentru a aduce arborele la adancimea maxima $q$. Daca $nr$ > $K$ atunci $q$ este prea mic. Altfel $q$ poate scadea in continuare. Pentru a afla $nr$ vom proceda in felul urmator. Fie $Di$ distanta de la radacina la nodul $i$. Sortam toate nodurile descrescator dupa $Di$. Parcurgem nodurile in ordinea sortarii. Sa zicem ca ne aflam la nodul $x$. Daca $Dx$ > $q$ atunci nodul $x$ trebuie urcat. Dar pentru ca nodul $x$ este cel mai de jos nod neurcat inca, vrem sa ducem nodul $x$ la nivelul $q$ schimband tatal celui de al $q-1$-lea tata al lui $x$. Facem acest lucru pentru a ridica cat mai multe noduri deasupra nivelului $q$. Fie $T$ al $q-1$-lea tata al lui $x$. Pentru a urca intreg subarborele lui $T$ parcurgem acest surarbore si marcam toate nodurile din subarbore ca fiind vizitate. Incrementam $nr$. Cand trecem la urmatorul nod ce trebuie ridicat, trebuie sa verificam in plus daca a fost vizitat (daca a fost in subarborele vreunui nod ridicat) ca sa stim ca nu trebuie ridicat. Trebuie de asemenea sa avem grija ca atunci cand parcurgem subarborele unui nod ce trebuie ridicat, sa nu revizitam nodurile ce au fost ridicate inainte pentru ca este inutil (sa nu parcurgem subarborii deja ridicati ai subarborelui ce vrem sa il ridicam in acest moment pentru ca nu este necesar; acest lucru ar duce la o complexitate mult mai mare).
 
Aceasta abordare duce la o complexitate $N$ log $N$.

private

public