Problem Background

JOI 2019 Final T5

Due to the large number of data points, only a portion of the data will be evaluated for this problem.

Problem Description

In the country of JOI, there are $N$ cities numbered from $1$ to $N$. These cities are connected by $N-1$ bidirectional roads, with the $i$-th road connecting cities $A_i$ and $B_i$. It is possible to reach any city from any other city.

JOI has special特产, each with a number between $1$ and $M$ inclusive, although not all integers from $1$ to $M$ may represent a special特产. Each city in JOI produces one special特产. City $j$ produces the特产 $C_j$. Multiple cities may produce the same特产.

The distance between two cities is defined as the minimum number of roads needed to travel from one city to the other. For a city $x$, a city $y$ ($y \neq x$) is defined as a unique city if and only if for any city $z$ ($z \neq x, z \neq y$), the distance between $x$ and $y$ is not equal to the distance between $x$ and $z$.

Mr. K, the Minister of Transportation in JOI, wants to know how many different special特产 can be produced by the unique cities for each city $j$.

Given the road information of JOI and the special特产 produced by each city, write a program to calculate the number of different special特产 that can be produced by the unique cities for each city.

Input Format

The first line contains two integers $N$ and $M$, as described in the problem.

The next $N-1$ lines each contain two integers $A_i$ and $B_i$, as described in the problem.

The last line contains $N$ positive integers, the $i$-th of which is $C_i$, as described in the problem.

Output Format

Output $N$ lines, the $i$-th line indicating the number of different special特产 that can be produced by the unique cities for city $i$.

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

Explanation for Sample #1:

For city $1$, its unique cities are cities $2$ and $3$. City $2$ produces特产 $2$ and city $3$ produces特产 $3$, totaling two different特产, so the answer is $2$.

For city $2$, there are no unique cities, so the output is $0$.

For city $3$, its unique city is city $1$, which produces特产 $1$, so the answer is $1$.

For city $4$, its unique cities are cities $1$ and $3$, both of which produce特产 $1$, so the answer is $1$.

For city $5$, its unique cities are cities $1$ and $3$, both of which produce特产 $1$, so the answer is $1$.

Note: No city produces特产 $3$.

For $4\%$ of the data, $N \le 2000$.

For another $32\%$ of the data, $M = 1$.

For another $32\%$ of the data, $M = N$ and $C_j = j$ for $1 \le j \le N$.

For $100\%$ of the data, $1 \le N \le 2 \times 10^5$, $1 \le M, A_i, B_i \le N$, $A_i \neq B_i$, $1 \le C_j \le M$.

见题面 Input 部分

见题面 Output 部分