== include(page="template/taskheader" task_id="rafaela") ==
Poveste și cerință...
Prințesa cu ochii verzi din regatul arborilor, Rafaela, trebuie să recupereze taxele de la toți cetățenii regatului. Astfel, formal, se dă un arbore cu $N$ noduri, în fiecare nod aflându-se inițial un număr dat de cetățeni. Rafaela ar dori să plaseze capitala regatului într-unul dintre noduri, însă datorită fluctuației numărului de cetățeni din regat, a întâmpinat o problemă pe care ar dori să o rezolve pe calculator. Astfel, ea va efectua anumite operații asupra arborelui pentru a lua, în final, o decizie. Operațiile sunt de tipul update/query și sunt descrise mai jos:
* $U nr id$ – caracterul $U$ urmat de două numere întregi, care reprezintă o operație de update și are semnificația: în nodul cu indicele $id$ apare un numar de $nr$ cetățeni (în caz că numărul este pozitiv) sau dispare un număr de $nr$ cetățeni (în cazul în care numărul este negativ);
* $Q id$ – caracterul $Q$ urmat de un număr întreg, reprezentând o operație de tip query la care voi trebuie să răspundeți: dacă am stabili capitala regatului în nodul cu indicele [$id$], atunci care ar fi muchia cea mai des utilizată (pe care se plimbă cei mai mulți cetățeni) dacă toți cetățenii ar decide să meargă din nodurile în care se află spre capitală? Cum pot exista mai multe astfel de muchii, Rafaela se mulțumește doar să aflați numărul de cetățeni care merg pe una dintre muchiile cele mai utilizate.
h2. Cerință
Dându-se un arbore cu $N$ noduri, numărul inițial de cetățeni din fiecare nod și $Q$ operații de tipul update/query, trebuie să răspundeți la operațiile de tip query.
h2. Date de intrare
Fișierul de intrare $rafaela.in$ ...
Fișierul de intrare $rafaela.in$ conține pe prima linie două numere naturale $N$ si [$Q$], separate printr-un spațiu, reprezentând numărul de noduri ale arborelui, respectiv numărul de operații efectuate. Pe următoarele $N - 1$ linii se află perechi de câte două numere naturale $a$ și [$b$], separate printr-un spațiu, reprezentând o muchie ([$a$] și $b$ reprezintă două noduri din arbore). Pe următoarea linie se află $N$ numere naturale separate prin câte un spațiu, numărul de pe poziția $i$ reprezentând numărul de cetățeni care se află inițial în nodul [$i$]. Pe următoarele $Q$ linii se află operații de tip update/query, o operație de update fiind codificată prin caracterul [$U$], iar o operație de tip query prin caracterul [$Q$]. În cazul în care este o operație de tip update, pe aceeași linie urmează încă două numere intregi $nr$ și [$id$], separate printr-un spațiu, unde $nr$ reprezintă numărul de cetățeni care apar/dispar în nodul [$id$]. În cazul în care este o operație de tip query, pe aceeași linie urmează un număr natural [$id$], care reprezintă nodul care va deveni capitală și pentru care vi se cere să aflați răspunsul.
h2. Date de ieșire
În fișierul de ieșire $rafaela.out$ ...
Fișierul de ieșire $rafaela.out$ va conține pe fiecare linie câte un număr întreg, reprezentând răspunsurile (în ordine) pentru fiecare operație de tip query din fișierul de intrare.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 200 000$
* $1 ≤ Q ≤ 200 000$
* Se garantează că numărul total de cetățeni, după fiecare operație update, se încadrează pe $32$ de biți cu semn.
* Se garantează că numărul de cetățeni dintr-un nod, după fiecare operație de update este un număr pozitiv (mai mare sau egal cu [$0$]).
h2. Exemplu
table(example).
|_. rafaela.in |_. rafaela.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 5
1 2
2 3
2 4
4 5
1 2 3 2 3
Q 2
U 10 3
Q 2
U -5 3
Q 1
| 5
13
15
|
h3. Explicație
...
Pentru primul query răspunsul este [$5$], muchia cea mai intens utilizată fiind cea dintre nodurile $2$ și $4$ (se deplasează către capitala $2$ toți cetățenii din nodurile $4$ și [$5$]).
Pentru al doilea query, răspunsul este [$13$], muchia cea mai utilizată fiind cea care unește nodul $2$ de nodul $3$ (nodul $3$ conține $13$ cetățeni, în urma operației update).
Pentru al treilea query, răspunsul este [$15$], muchia cea mai folosită fiind cea dintre nodul $1$ și nodul [$2$].
== include(page="template/taskfooter" task_id="rafaela") ==
