Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | djok.in, djok.out | Sursă | Algoritmiada 2019 Runda Finala |
| Autor | Adrian Budau, Tamio-Vesa Nakajima | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Djok
Tanaka a inceput sa joace un nou joc. In acest joc, exista N monstruleti (precum gandacul fantastic, soarecele fioros, condorul inalt). Fiecare monstrulet este caracterizat de o vitejie, si fiecare monstrulet se gaseste intr-o arena (precum arena info, sau arena arenelor); arenele sunt conectate de catre poteci. Acestea formeaza un arbore, daca potecile sunt considerate a fi muchii, si arenele noduri. Jocul se desfasoara astfel: Tanaka alege o arena de initiala, si controleaza monstruletul din acea arena. Tanaka poate acum sa se poate deplasa prin poteci, avand batalii cu monstrii din arenele la care ajunge. El va putea invinge doar monstrii care au vitejia cu cel mul K unitati mai mare ca a lui. Dupa oricare batalie castigata, vitejia fie ramane la fel daca monstruletul batut nu e mai puternic ca monstruletul controlat, fie creste la vitejia monstruletului invins. Pentru fiecare monstru initial, spuneti numarul maxim de monstrii pe care ii poate invinge Tanaka.
Date de intrare
Fişierul de intrare djok.in va contine, pe primul rand, numerele N si K.
Pe cel de al doilea rand, se vor gasi N numere, vitejiile mosntrilor, in ordine.
Pe urmatoarele N-1 linii vor urma perechi a b de indici, care reprezinta o poteca intre arenele a si b.
Date de ieşire
În fişierul de ieşire djok.out va contine N numere, rezultatele pentru cele N noduri.
Restricţii
- 1 ≤ N ≤ 150.000.
- 1 ≤ K, oricare vitejie ≤ 1.000.000.000.
- Pentru 10 puncte, N ≤ 100.
- Pentru alte 20 puncte, N ≤ 1.000.
- Pentru alte 45 puncte, N ≤ 70.000.
- Se considera invins si monstrul pe care il controleaza Tanaka
- Tanaka este obligat sa aiba o batalie cu monstrul dintr-o arena prima oara cand trece prin acea arena. Nu poate sa treaca de o arena daca nu poate bate monstrul corespunator.
Exemplu
| djok.in | djok.out |
|---|---|
| 5 1 1 2 4 5 6 1 2 2 3 3 4 4 5 | 2 2 5 5 5 |
| 5 3 13 7 20 14 14 4 3 5 2 4 5 2 1 | 4 1 5 4 4 |
