Fişierul intrare/ieşire:metro.in, metro.outSursăRMI 2016
AutorTeodor IonescuAdăugată deheracleRadu Muntean heracle
Timp execuţie pe test5.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Metro

În ultimii ani Institutul de Cercetare al Tulburărilor Compulsive a devenit supraaglomerat descoperind şi clasificând o multitudine de comportamente ciudate. Tu ai fost desemnat să investighezi una dintre aceste anomalii răspândite printre oamenii inocenţi care folosesc metroul.

Metroul este compus din N staţii conectate prin N-1 căi bidirecţionale şi M trenuri cu rute liniare, fiecare având un număr unic. Problema se referă la panourile informative localizate în staţie pe care se afişează în ordine numerele metrourilor ce trec prin respectiva staţie. Unul dintre pacienţi pretinde că de fiecare dată când vede o listă de numere întregi C0 , C1 , … , CL nu se poate abţine şi calculează suma numerelor cu indici pari S = C0 + C2 + C4 + … + C2K + … . O astfel de listă poate fi văzută pe fiecare dintre panourile informative aflate în staţii.

Înainte ca orice presupunere să poată fi făcută legat de cei afectaţi, trebuie să calculăm suma pentru fiecare din cele N panouri din staţii. Din păcate dacă le calculăm de mână există o şansă relativ sigură să ajungem şi noi afectaţi de o astfel de boală. Pentru asta trebuie să scrii un program ce le va calcula pentru tine, astfel mintea ta va fi protejată de tulburare.

Fiind dat un număr de staţii, N, felul în care sunt conectate cât şi cele M metrouri calculaţi suma necesară pentru fiecare staţie.

Date de intrare

Fişierul metro.in conţine două numere întregi pe prima linie, N şi M. Pe următoarele N-1 linii se află două numere întregi xi, yi reprezentând calea între staţiile xi si yi. Următoarele M linii descriu câte un metrou folosind trei numere întregi ai, bi şi oi cu semificaţia ca metroul numerotat cu oi merge de la staţia ai la bi.

Date de ieşire

Fişierul metro.out trebuie să conţină N linii. Linia i conţine un singur număr şi anume suma calculată pentru staţia i. Dacă nu exista niciun tren ce trece prin statia i afisati 0 pe linia respectiva.

Restricţii

1 ≤ N ≤ 200,000
1 ≤ M ≤ 200,000
1 ≤ noi ≤ M pentru toţi 1 ≤ i ≤ M
Se garantează că se poate ajunge dintr-o staţie în oricare alta

Exemplu

metro.inmetro.out
6 4
1 2
2 4
2 6
1 3
5 2
5 6 3
4 5 1
4 3 2
1 2 4
2
4
2
1
1
3

Explicaţie

Panourile afişează următoarele numere:

Staţia 1: 2 4
Staţia 2: 1 2 3 4
Staţia 3: 2
Staţia 4: 1 2
Staţia 5: 1 3
Staţia 6: 3

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?