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

Points: 25 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

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$ $N$ nodes labeled from $1$ $1$ to $N$ $N$ . Being a tree, it has $N-1$ $N - 1$ edges and each edge has distance $1$ $1$ . Furthermore, each node has an additional value $a_i$ $a_{i}$ associated with it. Being a magical panda, Larry can teleport from a node $u$ $u$ to any node $v$ $v$ with distance less than or equal to a given constant $D$ $D$ from $u$ $u$ . The teleportation comes at the cost of $a_v$ $a_{v}$ . For each node $v$ $v$ , what is the minimum cost for Larry to reach $v$ $v$ if he starts the game at node $1$ $1$ ?

Constraints

$1 \le D < N \le 2 \times 10^5$ $1 \leq D < N \leq 2 \times 10^{5}$

$1 \le a_i \le 10^9$ $1 \leq a_{i} \leq 10^{9}$

Subtask 1 [10%]

$a_i = 1$ $a_{i} = 1$

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line will contain two integers, $N$ $N$ and $D$ $D$ .

The following line will contain $N$ $N$ integers $a_i$ $a_{i}$ .

The following $N-1$ $N - 1$ lines will each contain two integers, $u_i$ $u_{i}$ and $v_i$ $v_{i}$ , denoting an edge between nodes $u_i$ $u_{i}$ and $v_i$ $v_{i}$ .

Output Specification

Output $N$ $N$ space separated integers, the $v$ $v$ -th of which represents the minimum cost for Larry to reach node $v$ $v$ .

Sample Input 1

Copy

2 1
1 1
1 2

Sample Output 1

Copy

0 1

Sample Input 2

Copy

6 3
100 100 100 100 100 1
1 2
2 3
3 4
4 5
3 6

Sample Output 2

Copy

0 100 100 100 101 1

Comments

1

HisMonDon commented on Feb. 21, 2024, 2:26 a.m.

i clicked on this problem because i thought it was clash related...

5

X_Ray commented on Aug. 24, 2022, 11:57 p.m.

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.