infoarena

Comentarii la articolul Tree decompositions (http://infoarena.ro/tree-decompositions)

Poate povesti cineva puțin mai mult la ce se referă când zice "Se elimina cel mai lung lant radacina-frunza din arbore si se apeleaza recursiv pentru restul componentelor conexe" și cum se face update? :)

Iniţial, consideri cel mai lung lanţ (cu cele mai multe noduri) de la rădăcină la oricare din frunze. Reţii acest lanţ şi îl scoţi din arbore. Astfel, dacă lanţul ăsta „taie” arborele pe jumătate o să ai doi arbori separaţi pe care repeţi procedeul. Apelând recursiv rezolvi aceeaşi problemă. Şi vei reţine astfel o mulţime de lanţuri ce reprezintă descompunerea arborelui. Ulterior, pe ele faci operaţiile.

Query-urile se fac pe un arbore de intervale. Deci, un update din problemă se reduce la un update pe un arbore de intervale. Mai întreabă dacă nu ai înţeles.

Nu am prea înțeles cum fac acea descompunere, pentru că dacă scot un lanț din arbore e foarte posibil să apară o grămadă de arbori mai mici, și ce se reține mai exact în Path[].parrent?

Intocmai. Apar o gramada de arbori mai mici si apelezi aceeasi functie recursiv pentru fiecare dintre ei. Parent e lantul de care trebuie sa unesti lantul tau ca sa il pui pe drumul spre radacina.

Dar numărul de lanțuri nu poate să fie mai mare de sqrt(N)? De exemplu, dacă am N-1 noduri sunt legate de rădăcină, nu vor fi N-1 lanțuri?

Daca scoti un lant din cele N-1, scoti radacina => raman N - 2 frunze.

Ba da, numarul total de lanturi poate sa fie O(N). Ceea ce ne intereseaza este ca numarul de lanturi prin care treci de la orice nod la radacina sa fie de ordinul O(sqrt(N)).

Scrie în articol, deasupra figurii 2... „Este evident ca memoria ocupata este O(N), fiecare nod fiind inclus intr-un singur lant. Numarul maxim de lanturi prin care putem trece pornind din radacina pana intr-una din frunze, este O(sqrt(N)).”