Fișierul intrare/ieșire rafaela.in, rafaela.out Sursă Lot Sovata 2014
Autor Andrei Ciocan | Vlad Ionescu Adăugată de avatar spatarel Spatarel Dan-Constantin spatarel
Timp de execuție pe test 1 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

Rafaela (lot liceu)

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.

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.

Date de intrare

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.

Date de ieșire

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.

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).

Exemplu

rafaela.in rafaela.out
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

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii