An Animal Contest 5 P3 - Ski Resort

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 256M

Problem type

Larry the magical panda has recently purchased a ski resort. Being an avid fan of bamboo trees, he ensured that the ski hills resembled a rooted tree. There are N breakpoints, which are given a unique ID from 1 to N inclusive. The breakpoint with the ID 1 will always be the root. There are N-1 hills, which connect these breakpoints. The i-th hill has a difficulty level of d_i. There will be K fellow pandas, the i-th of which with a skill level of s_i, who will start at breakpoint 1 and begin skiing. The following process is used by them to determine which hill they will go down:

  1. If there are no hills connecting to their current breakpoint, they will stop skiing. Note that a panda will never use a hill that they have already used (otherwise, they would be going uphill).
  2. The panda will consider all difficulty levels of the hills connecting to their breakpoint, and will go down the hill that minimizes |s_i - d_i|. If there is a tie, they will go down the hill with the lower difficulty level. Out of the hills that they consider, there will never be two with equal difficulty.
  3. Go back to step 1.

Larry wants you to help him determine how many pandas will visit each breakpoint so he can efficiently determine how to ambush all the skiers.


1 \le N, K \le 2 \times 10^5

1 \le d_i, s_i \le 10^9

A panda will never have to choose between two hills of equal difficulty.

Input Specification

The first line contains 2 integers N and K.

The next N-1 lines contain 3 integers, a_i, b_i, and d_i, representing a hill between breakpoint a_i and b_i with a difficulty level of d_i.

The next line contains K integers s_1, s_2, \dots, s_k, representing the skill level of the pandas.

Output Specification

Output a single line containing N integers, with the i-th integer denoting the number of pandas who will visit the i-th breakpoint.

Sample Input 1

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

Sample Output 1

6 5 1 1 4

Sample Input 2

8 6
1 2 3
2 3 3
2 4 4
4 5 1
4 6 3
2 7 6
1 8 4
1 2 3 4 5 6

Sample Output 2

6 3 3 0 0 0 0 3


There are no comments at the moment.