== 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. Cerinta
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$} si $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$ si $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") ==
