Fişierul intrare/ieşire:heavypath.in, heavypath.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.6 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

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.inheavypath.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:

  1. Nodul x este o frunza. In acest caz, cream un lant nou care contine doar pe x.
  2. 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.

Probleme propuse

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content