Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2011-08-17 12:13:29.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:heavypath.in, heavypath.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată deGavrilaVladGavrila Vlad •GavrilaVlad
Timp execuţie pe test0.3 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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?