An Animal Contest 5 P6 - Larry Finally Uses His Magical Powers

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

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?

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.


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.

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


There are no comments at the moment.