Unique Cities

JOI Country has $N$ cities, numbered from $1$ through $N$. The cities are connected by $N-1$ roads. The $i$-th road ($1 \le i \le N-1$) connects cities $A_i$ and $B_i$ in both directions. From any city to any other city, you can travel using some roads.

JOI Country has some local specialties. Each kind of specialty is assigned an integer from $1$ to $M$, inclusive. Some integers may not correspond to any specialty in JOI Country. Each city produces one kind of specialty. City $j$ ($1 \le j \le N$) produces specialty $C_j$. Multiple cities may produce the same kind of specialty.

The distance between two cities is the minimum number of roads needed to travel from one to the other. For city $x$ ($1 \le x \le N$), city $y$ ($1 \le y \le N$, $y \ne x$) is a unique city if, for every city $z$ ($1 \le z \le N$, $z \ne x$, $z \ne y$), the distance between $x$ and $y$ differs from the distance between $x$ and $z$.

Mr. K, the Minister of Transport in JOI Country, wants to know, for each $j$ ($1 \le j \le N$), the number of kinds of specialties produced in the unique cities for city $j$. Write a program that calculates this value for every city.

The first line contains $N$ and $M$. Each of the next $N-1$ lines contains $A_i$ and $B_i$. The last line contains $N$ integers $C_1 \cdots C_N$, separated by spaces.

Print $N$ lines. The $j$-th line contains the number of kinds of specialties produced in the unique cities for city $j$.

• $2 \le N \le 200000$
• $1 \le M \le N$
• $1 \le A_i \le N$ ($1 \le i \le N-1$), $1 \le B_i \le N$ ($1 \le i \le N-1$)
• $A_i \ne B_i$ ($1 \le i \le N-1$)
• From any city to any other city, you can travel using some roads.
• $1 \le C_j \le M$ ($1 \le j \le N$)