P6118 [JOI 2019 Final] Unique Cities / Unique Cities

JOI 2019 Final T5.

JOI Country has $N$ cities, numbered from $1$ to $N$. These cities are connected by $N - 1$ bidirectional roads. The $i$-th road connects cities $A_i$ and $B_i$. From any city, you can reach all cities. JOI Country has some local products. Each product type is numbered between $1$ and $M$ (including $1$ and $M$), but some integers from $1$ to $M$ may not correspond to any product in JOI Country. Each city in JOI Country produces exactly one product. The product produced by city $j$ is $C_j$. Multiple cities may produce the same product. We define the distance between two cities as the minimum number of roads that must be passed through to go from one city to the other. For a city $x$, we define a city $y$ ($y \neq x$) to be 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 of JOI Country, wants to know how many different kinds of products can be produced in total by the **unique cities** of city $j$. Given the road information of JOI Country and the product produced by each city, write a program to compute, for each city, how many different kinds of products can be produced in total by its **unique cities**.

The first line contains two integers $N, M$, as described in the statement. The next $N - 1$ lines each contain two integers $A_i, B_i$, as described in the statement. The last line contains $N$ positive integers. The $i$-th integer is $C_i$, as described in the statement.

Output $N$ lines. The $i$-th line should contain the number of different kinds of products that can be produced in total by the unique cities of city $i$.

Sample Explanation 1: For city $1$, its unique cities are cities $2$ and $3$. City $2$ produces product $2$, and city $3$ produces product $3$, so there are $2$ kinds of products in total. Therefore the answer is $2$. For city $2$, there are no unique cities, so output $0$. For city $3$, its unique city is city $1$. City $1$ produces product $1$, so the answer is $1$. For city $4$, its unique cities are cities $1$ and $3$. Both cities $1$ and $3$ produce product $1$, so the answer is $1$. For city $5$, its unique cities are cities $1$ and $3$. Both cities $1$ and $3$ produce product $1$, so the answer is $1$. Note: No city produces product $3$. For $4\%$ of the testdata, $N \le 2000$. For another $32\%$ of the testdata, $M = 1$. For another $32\%$ of the testdata, $M = N, C_j = j (1 \le j \le N)$. For $100\%$ of the testdata, $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$. Translated by ChatGPT 5