Fişierul intrare/ieşire:rafaela.in, rafaela.outSursăLot Sovata 2014 Seniori Baraj 2
AutorAndrei Ciocan, Vlad IonescuAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Rafaela

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.

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.

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

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?