Larry the magical panda is playing a new game once again! This time, having gotten bored of playing with bamboo sticks, Larry is playing the game on an entire bamboo tree with 
~N~ nodes labeled from 
~1~ to ~N~. Being a tree, it has 
~N-1~ edges and each edge has distance ~1~. Furthermore, each node has an additional value 
~a_i~ associated with it. Being a magical panda, Larry can teleport from a node 
~u~ to any node 
~v~ with distance less than or equal to a given constant 
~D~ from ~u~. The teleportation comes at the cost of 
~a_v~. For each node ~v~, what is the minimum cost for Larry to reach ~v~ if he starts the game at node ~1~?
Constraints
~1 \le D < N \le 2 \times 10^5~
~1 \le a_i \le 10^9~
Subtask 1 [10%]
~a_i = 1~
Subtask 2 [90%]
No additional constraints.
Input Specification
The first line will contain two integers, ~N~ and ~D~.
The following line will contain ~N~ integers ~a_i~.
The following ~N-1~ lines will each contain two integers, 
~u_i~ and 
~v_i~, denoting an edge between nodes ~u_i~ and ~v_i~.
Output Specification
Output ~N~ space separated integers, the ~v~-th of which represents the minimum cost for Larry to reach node ~v~.
Sample Input 1
2 1
1 1
1 2
Sample Output 1
0 1
Sample Input 2
6 3
100 100 100 100 100 1
1 2
2 3
3 4
4 5
3 6
Sample Output 2
0 100 100 100 101 1
Comments
i clicked on this problem because i thought it was clash related...
I believe that there are anti-hashing cases in batch 1. I recommend using a custom hash function if you choose to use unordered_map or gp_hash_table.