| Fişierul intrare/ieşire: | heavypath.in, heavypath.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Heavy Path Decomposition
Se da un arbore cu N noduri, fiecare avand asociata o valoare vi, 1 ≤ i ≤ N. Se dau M operatii de forma (t, x, y), cu urmatoarea semnificatie:
- daca t este 0, operatia este de tipul update, iar valoarea vx asociata nodului cu indicele x devine y;
- daca t este 1, operatia este de tipul query si se cere sa se afiseze valoarea maxima asociata unui nod aflat pe lantul elementar care uneste nodurile x si y.
Date de intrare
Pe prima linie a fişierul de intrare heavypath.in se vor afla valorile N si M. Pe urmatoarea linie se vor afla N numere naturale, al i-lea dintre acestea reprezentand valoarea vi. Pe urmatoarele N-1 linii se vor afla N-1 perechi de numere (a, b), cu semnificatia ca exista o muchie intre nodurile a si b. Ultimele M linii vor contine tripletele (t, x, y), descriind operatiile ce vor fi efectuate.
Date de ieşire
În fişierul de ieşire heavypath.out se vor afisa raspunsurile pentru operatiile de tipul query.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 100 000
- 0 ≤ vi ≤ 2 000 000 000, initial si dupa oricare operatie.
Exemplu
| heavypath.in | heavypath.out |
|---|---|
| 9 7 5 4 9 7 5 8 2 11 100 1 2 2 3 2 7 3 4 3 5 3 6 7 8 8 9 1 6 1 1 6 8 1 9 4 1 4 7 0 3 1 1 4 7 1 5 2 | 9 11 100 9 7 5 |
Indicatii de rezolvare
Pentru a usura rezolvarea acestei probleme, vom considera ca nodul 1 este radacina arborelui. De asemenea, definim nivelul unui nod x din arbore ca fiind numarul de noduri din lantul elementar care uneste radacina de nodul x. Mai definim parintele unui nod x ca fiind singurul vecin al sau cu nivel mai mic decat al lui x si parintele unui lant ca fiind parintele nodului aflat pe nivelul cel mai mic al lantului respectiv.
Cea mai simpla rezolvare, de complexitate O(N * M), va parcurge nod cu nod fiecare lant ce apare la un query, retinand valoarea maxima care apare pe acest drum. Pornind initial cu doi pointeri din nodurile x si y, ne vom muta, la fiecare pas, din nodul aflat pe cel mai mare nivel in parintele acestuia, pana cand cei doi pointeri indica spre acelasi nod, LCA-ul nodurilor x si y. Operatia de update se realizeaza in O(1), inlocuind valoarea veche vx cu y. Aceasta solutie ar trebui sa obtina 20 de puncte.
Stim ca putem afla maximul dintr-o subsecventa a unui sir cu ajutorul unui arbore de intervale. Urmatoarea solutie se foloseste de aceasta structura pentru a reduce complexitatea la O(M * √N * log N). Nu putem aplica un arbore de intervale pe arborele nostru, astfel ca suntem nevoiti sa il descompunem in lanturi. Aceasta descompunere se poate face cu ajutorul unei parcurgeri DF. Astfel, pentru un nod x pentru care am apelat in prealabil functia DF pentru toti fiii sai, avem urmatoarele cazuri:
- Nodul x este o frunza. In acest caz, cream un lant nou care contine doar pe x.
- Nodul x este un nod intern. In aceasta situatie, il adaugam pe x la cel mai lung lant care se termina intr-unul din fiii sai.
Pentru fiecare lant astfel obtinut vom sorta nodurile crescator dupa nivel, pentru a putea tine un arbore de intervale care va retine in intervalul [x, y] valoarea maxima a unui nod aflat, in lantul care-l contine, intre pozitiile x si y, inclusiv. Pentru fiecare nod x vom retine pozx, pozitia sa in lantul de care apartine. Acum o operatie de update (0, x, y) va putea fi efectuata in O(log N), actualizand arborele de intervale asociat lantului care contine nodul x. Un query (1, x, y) se va rezolva astfel: daca x si y apartin aceluiasi lant, interogam pentru acesta intervalul [min(pozx, pozy), max(pozx, pozy)] si actualizam solutia curenta daca este cazul. Altfel, daca parintele lantului lui x are nivelul mai mic decat parintele lantului lui y, interschimbam pe x si y. Vom interoga, pentru lantul lui x, intervalul [1, pozx], x primeste valoarea parintele lantului lui x si reluam algoritmul pentru noua pereche (x, y). Complexitatea finala O(√N * log N) pentru un query se datoreaza faptului ca drumul dintre x, respectiv y si LCA (x, y) va traversa maxim √N lanturi, aceasta proprietate datorandu-se modului de constructie al lanturilor. Aceasta solutie ar trebui sa obtina 60 de puncte.
Pentru a reduce complexitatea la O(M * log2 N), vom construi lanturile diferit, modificand abordarea in cazul 2 al DF-ului. Astfel, in loc sa unim un nod x cu cel mai lung lant care se termina intr-unul din fiii sai, il vom uni cu lantul asociat fiului care cuprinde cele mai multe noduri in subarborele sau. Aceasta modalitate garanteaza ca drumul dintre x, respectiv y si LCA (x, y) va traversa maxim log N lanturi. Aceasta solutie obtine 100 de puncte.
Precedentele doua abordari poarta numele de Longest Path Decomposition, respectiv Heavy Path Decomposition, ambele fiind tratate in acest articol.
