## An Animal Contest 5 P3 - Ski Resort

View as PDF

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

Author:
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 breakpoints, which are given a unique ID from to inclusive. The breakpoint with the ID will always be the root. There are hills, which connect these breakpoints. The -th hill has a difficulty level of . There will be fellow pandas, the -th of which with a skill level of , who will start at breakpoint 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 . 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.

#### Constraints

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

#### Input Specification

The first line contains integers and .

The next lines contain integers, , , and , representing a hill between breakpoint and with a difficulty level of .

The next line contains integers , representing the skill level of the pandas.

#### Output Specification

Output a single line containing integers, with the -th integer denoting the number of pandas who will visit the -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