h2. Pentru 10 puncte

Vom mentine sirul $next[i]$ si vom face operatiile in ordinea data. La update, putem parcurge tot sirul $next[]$ si daca $next[i] == x$, il schimbam in $next[x]$. La query, putem merge din $a$ in $next[a]$ pana cand am mai ajuns intr-un nod vizitat la acest query si vom retine care este timpul $timpA$ la care vom deschide fiecare videclip vizitat. Apoi din $b$ vom face o parcurgere asemanatoare. La final, se considera videoclipurile vizitate atat din $a$, cat si din $b$, si se ia acela pentru care $max(timpA, timpB)$ este cat mai mic. Daca nu exista nod vizitat de ambii, afisam infinit.

Vom mentine sirul $next[i]$ si vom face operatiile in ordinea data. La update, putem parcurge tot sirul $next[]$ si daca $next[i] == x$, il schimbam in $next[x]$. La query, putem merge din $a$ in $next[a]$ pana cand am mai ajuns intr-un nod vizitat la acest query si vom retine care este timpul $timpA$ la care vom deschide fiecare videoclip vizitat. Apoi din $b$ vom face o parcurgere asemanatoare. La final, se considera videoclipurile vizitate atat din $a$, cat si din $b$, si se ia acela pentru care $max(timpA, timpB)$ este cat mai mic. Daca nu exista nod vizitat de ambii, afisam infinit.

h2. Pentru 100 de puncte

* Afla distanta de la un nod la un stramos al sau intr-un arbore
* Afla distanta de la un nod la altul intr-un ciclu

Aceste operatii ne duc cu gandul la liniarizarea plus-minus a arborilor si la mentinerea unui arbore indexat binar atat peste aceste liniarizari, cat si peste a ciclilor. Putem mentine un singur aib pentru toti arborii, daca le concatenam liniarizarile. Asemanator putem proceda cu ciclii. Mentionam ca mai trebuie sa obtinem si $lca$ in timp logaritmic.

Aceste operatii ne duc cu gandul la liniarizarea plus-minus a arborilor si la mentinerea unui arbore indexat binar atat peste aceste liniarizari, cat si peste ciclii. Putem mentine un singur aib pentru toti arborii, daca le concatenam liniarizarile. Asemanator putem proceda cu ciclii. Mentionam ca mai trebuie sa obtinem si $lca$ in timp logaritmic.

Complexitate finala: timp $O((N + Q) * logN)$, memorie $O(N * logN)$ (pentru precalcularea necesara pentru $lca$).

private

protected