Problem Description

In the Kingdom of JOI, there are $ N $ cities numbered from $ 1 $ to $ N $. These cities are connected by $ N - 1 $ roads. The $ i $-th ($1 \leq i \leq N - 1$) road connects city $ A_i $ and city $ B_i $ and is bidirectional. Any city can be reached from any other city by traveling through some roads.

There are several specialty products in the Kingdom of JOI. Each specialty product is assigned a number between $ 1 $ and $ M $ (some numbers might not correspond to any specialty product produced in the Kingdom). Each city produces one specialty product. City $ j $ ($1 \leq j \leq N$) produces specialty product $ C_j $. Multiple cities may produce the same type of specialty product.

The distance between two cities is defined as the minimum number of roads needed to travel between them. City $ y $ ($1 \leq y \leq N, y \neq x$) is considered a unique city from the perspective of city $ x $ ($1 \leq x \leq N$) if, for all cities $ z $ ($1 \leq z \leq N, z \neq x, z \neq y$), the distance between city $ x $ and city $ y $ is different from the distance between city $ x $ and city $ z $.

K, the chairman of the Kingdom of JOI, wants to know, for each city $ j $ ($1 \leq j \leq N$), how many different types of specialty products are produced in unique cities from the perspective of city $ j $.

Given the road information of the Kingdom of JOI and the numbers of the specialty products produced in each city, create a program to determine, for each city, how many different types of specialty products are produced in unique cities from its perspective.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $\vdots$ $ A_{N-1} $ $ B_{N-1} $ $ C_1 $ $\cdots$ $ C_N $

Output Format

Output $ N $ lines to the standard output. The $ j $-th line ($1 \leq j \leq N$) should contain the number of different types of specialty products produced in unique cities from the perspective of city $ j $.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
0
1
1
1

Sample Input #2

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

Sample Output #2

1
1
1
0
1
1
1

Sample Input #3

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

Sample Output #3

4
3
4
2
0
2
2
0
3
2

Sample Input #4

22 12
9 6
12 13
4 20
21 22
3 19
2 9
6 18
18 11
18 3
16 2
6 4
3 17
16 10
8 16
22 1
16 14
15 8
9 21
2 12
21 5
12 7
1 1 4 8 4 11 7 6 7 11 6 11 10 4 7 5 3 12 9 6 12 2

Sample Output #4

2
0
1
1
1
1
1
0
0
1
2
0
1
1
2
0
2
1
2
3
0
0

Notes/Hints

Constraints

• $2 \leq N \leq 200,000$.
• $1 \leq M \leq N$.
• $1 \leq A_i \leq N$ ($1 \leq i \leq N - 1$), $1 \leq B_i \leq N$ ($1 \leq i \leq N - 1$).
• $ A_i, B_i $ ($1 \leq i \leq N - 1$).
• Any city can be reached from any other city by traveling through some roads.
• $1 \leq C_j \leq M$ ($1 \leq j \leq N$).

Subtasks

1. ($ 4 $ points) $N \leq 2,000$.
2. ($ 32 $ points) $ M = 1 $.
3. ($ 32 $ points) $ M = N $, $ C_j = j $ ($1 \leq j \leq N$).
4. ($ 32 $ points) No additional constraints.

Sample Explanation 1

From the perspective of city $ 1 $, the unique cities are cities $ 2, 3 $, and the specialty products produced there are $ 2, 1 $, so the answer is $ 2 $ types. From the perspective of city $ 2 $, there are no unique cities, so the answer is $ 0 $ types. From the perspective of city $ 3 $, the unique city is city $ 1 $, and the specialty product produced there is $ 1 $, so the answer is $ 1 $ type. From the perspective of city $ 4 $, the unique cities are cities $ 1, 3 $, and both produce the specialty product $ 1 $, so the answer is $ 1 $ type. From the perspective of city $ 5 $, the unique cities are cities $ 1, 3 $, and both produce the specialty product $ 1 $, so the answer is $ 1 $ type. Note that the specialty product with number $ 3 $ does not exist.

Sample Explanation 2

This input example satisfies the constraints of Subtask $ 2 $.

Sample Explanation 3

This input example satisfies the constraints of Subtask $ 3 $.

见题面 Input 部分

见题面 Output 部分