h2. 'CT':problema/ct

Se fixeaza radacina arborelui intr-un nod (sa zicem nodul $1$). Pentru fiecare din cele $K$ perechi de orase se calculeaza $LCA$-ul (lowest common ancestor = cel mai apropiat stramos comun). Se poate folosi orice metoda eficienta de determinarea a $LCA$-ului: de exemplu, pentru fiecare nod $i$ se pot memora $O(logN)$ valori, $stramos[i][j]$, reprezentand stramosul aflat cu $2^j^$ nivele mai sus in arbore (cu $j$ incepand de la $0$), iar cu aceste valori, $LCA$-ul a oricare $2$ noduri se poate determina in timp $O(logN)$. Se sorteaza apoi $LCA$-urile tuturor perechilor, in functie de nivelul din arbore ($LCA$-urile de pe un nivel mai jos aflandu-se inaintea celor de pe un nivel mai ridicat). In continuare, vom parcurge $LCA$-urile in ordinea sortata. Pentru a rezolva problema, avem acum $2$ posibilitati:
 
* Vom renumerota nodurile conform unei parcurgeri in adancime (DF), astfel incat toate nodurile din subarborele oricarui nod $i$ sa formeze un interval de numere consecutive. Apoi vom tine un arbore de intervale pentru aceste numere. In arborele de intervale vom memora daca un nod (identificat prin numarul asociat lui din cadrul parcurgerii DF) a fost eliminat din arbore sau nu. Pentru fiecare $LCA$, in ordinea precizata mai sus, vom verifica daca cel putin unul din cele $2$ noduri al caror $LCA$ este a fost deja eliminat din arbore. Daca nu a fost eliminat nici unul, vom selecta $LCA$-ul acestora ca oras ce va fi bombardat si vom marca ca intreg intervalul de numere corespunzator subarborelui $LCA$-ului a fost eliminat din arbore. Complexitatea acestei variante este $O(K*logN)$, plus complexitatea determinarii celor $K LCA$-uri (care ar putea fi $O(N*logN + K*logN)$.
* A doua varianta nu mai necesita o renumerotare si utilizarea unui arbore de intervale, insa mentine ideea de a memora pentru fiecare nod daca acesta a fost eliminat sau nu din arbore. Parcurgem $LCA$-urile si verificam pentru fiecare daca cel putin unul din cele $2$ noduri din perechea de noduri pentru care a fost calculat $LCA$-ul a fost deja eliminat din arbore. Daca nici unul din cele $2$ noduri nu a fost eliminat din arbore, vom marca $LCA$-ul ca fiind oras ce va fi bombardat si apoi vom efectua o parcurgere DF pentru a marca toate nodurile din subarborele acestuia ca fiind eliminate. Optimizarea importanta este ca daca, in cadrul acestei parcurgeri, intalnim un nod deja marcat ca fiind eliminat, nu vom parcurge subarborele acestuia. In felul acesta, fiecare nod este marcat ca find eliminat cel mult o singura data, iar complexitatea acestei etape este $O(K + N)$.
 

h2. 'Swap':problema/swap
h2. 'Obj':problema/obj