heavypath

Heavy Path Decomposition

== include(page="template/taskheader" task_id="heavypath") ==

Poveste şi cerinţă...

Se da un arbore cu $N$ noduri, fiecare avand asociata o valoare $v{~i~}$, $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 $v{~x~}$ 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$.

h2. Date de intrare

Fişierul de intrare $heavypath.in$ ...

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 $v{~i~}$. 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.

h2. Date de ieşire

În fişierul de ieşire $heavypath.out$ ...

În fişierul de ieşire $heavypath.out$ se vor afisa raspunsurile pentru operatiile de tipul query.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 100 000$
* $0 ≤ v{~i~} ≤ 2 000 000 000$, initial si dupa oricare operatie.

h2. Exemplu