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

Cum se trimit solutii?