Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | viteza.in, viteza.out | Sursă | infoarena 2.0 |
| Autor | Andrei Parvu | Adăugată de |  Andrei Parvu •andrei.12 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Viteza
De curând, Alex şi-a luat o maşină nouă, şi este dornic să o testeze pe drumurile din Bucureşti. Harta capitalei poate fi reprezentată prin N intersecţii şi prin străzi bidirecţionale care unesc aceste intersecţii. Alex cunoaşte că poate ajunge din orice intersecţie în oricare alta urmând doar străzile existente. Mai mult, între oricare două intersecţii există un drum unic (reţeaua stradală este de fapt un arbore).
Fiecare intersecţie are asociată o limită de viteză, reprezentată printr-un număr natural. Din cauze încă neclare, limitele de viteză nu există decât in intersecţii, nu şi pe străzile care le unesc.
Deoarece Alex este un şofer responsabil, el nu doreşte să depăşescă limitele de viteză din intersecţii, dar totuşi doreşte să meargă cu o viteză cât mai mare. Astfel el îşi pune mai multe întrebări de forma: câte intersecţii de pe drumul dintre x şi y au limita de viteză mai mică sau egală cu k?
Pentru că sunteţi cel mai bun prieten al lui Alex, este datoria voastră să îl ajutaţi şi să îi răspundeţi la întrebări.
Date de intrare
Pe prima linie a fişierului viteza.in se găsesc două numere N şi M, numărul de intersecţii, respectiv numărul de întrebări ale lui Alex. Pe următoarele N - 1 linii se găsesc câte 2 numere pe linie, x şi y reprezentând faptul că există un drum între intersecţia x şi intersecţia y.
Pe linia N + 1 se găsesc N numere naturale, al i-lea număr reprezentând limita de viteză din intersecţia i.
Următoarele M linii descriu întrebările: pe fiecare linie sunt 3 numere x, y şi k, reprezentând întrebarea: câte intersecţii de pe drumul dintre x şi y (inclusiv x şi y) au limita de viteză mai mică sau egală cu k.
Date de ieşire
Fişierul viteza.out trebuie să conţina M linii, fiecare linie având răspunsul la a i–a întrebare.
Restricţii
- 1 ≤ N,M ≤ 100000
- 1 ≤ x,y ≤ N
- limitele de viteza din intersecţii, cât şi numerele k ale întrebărilor sunt ≤ 100000
Exemplu
| viteza.in | viteza.out |
|---|---|
| 5 3 1 2 2 3 2 4 1 5 4 5 7 1 2 4 3 6 3 5 1 4 1 1 | 2 0 1 |
Explicaţie
...
