Hamako Online Judge

TLE
2sec

MLE
256MB

得点
100

問題

JOI国には $N$ 個の都市があり，$1$ から　$N$ までの番号がついている．これらの都市は $N - 1$ 本の道路で結ばれている．$i$ 番目($1 \leqq i \leqq N - 1$)の道路は都市 $A_i$ と都市 $B_i$ を結んでおり，双方向に通行可能である．どの都市からどの都市へも何本かの道路を通行することで移動できる．
JOI国にはいくつかの特産品が存在する．特産品には，種類を表す $1$ 以上 $M$ 以下の番号が付けられている(JOI国で生産されている特産品に対応していない番号があるかもしれない)．各都市は $1$ つ以上の特産品を生産しており，都市 $j(1 \leqq j \leqq N)$では特産品 $C_j$ を生産している．複数の都市が同じ種類の特産品を生産することがあるかもしれない．
$2$ つの都市の間の距離は，その間を移動するために通る道路の本数の最小値である．都市 $x(1 \leqq x \leqq N)$から見て都市 $y(1 \leqq y \leqq N, y \neq x)$が珍しい都市であるとは，すべての都市 $z(1 \leqq z \leqq N, z \neq x, z \neq y)$について，都市 $x, y$ 間の距離と都市 $x, z$ 間の距離が異なることを意味する．
JOI国の大臣であるK理事長は，すべての $j(1 \leqq j \leqq N)$について，都市 $j$ から見て珍しい都市で生産されている特産品が何種類あるかを知りたい．
JOI国の道路の情報と，各都市で生産されている特産品の番号が与えられたとき，各都市ごとに，その都市から見て珍しい都市で生産されている特産品が何種類あるかを求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$
$A_1$ $B_1$
:
$A_{N-1}$ $B_{N-1}$
$C_1$ … $C_N$

出力

標準出力に，$N$ 行で出力せよ．$j$ 行目($1 \leqq j \leqq N$)には，都市 $j$ から見て珍しい都市で生産される特産品が何種類あるかを出力せよ.

制約

$2 \leqq N \leqq 200000$.
$1 \leqq M \leqq N$.
$1 \leqq A_i \leqq N(1 \leqq i \leqq N - 1), 1 \leqq B_i \leqq N(1 \leqq i \leqq N - 1)$.
$A_i \neq B_i(1 \leqq i \leqq N - 1)$.
どの都市からどの都市へも何本かの道路を通行することで移動できる.
$1 \leqq C_j \leqq M(1 \leqq j \leqq N)$.

小課題

(4 点) $N \leqq 2000$.
(32 点) $M = 1$.
(32 点) $M = N, C_j = j(1 \leqq j \leqq N)$.
(32 点) 追加の制約はない.

入出力例

入力例 1

出力例 1

都市 $1$ から見て珍しい都市は $2$, $3$ であり，そこで生産される特産品は特産品 $2$, $1$ なので，答えは $2$ 種類である．
都市 $2$ から見て珍しい都市は存在しないので，答えは $0$ 種類である．
都市 $3$ から見て珍しい都市は $1$ であり，そこで生産される特産品は特産品 $1$ なので，答えは $1$ 種類である．
都市 $4$ から見て珍しい都市は都市 $1$, $3$ であり，どちらの都市においても生産される特産品は特産品 $1$ なので，答えは $1$ 種類である．
都市 $5$ から見て珍しい都市は $1$, $3$ であり，どちらの都市においても生産される特産品は特産品 $1$ なので，答えは $1$ 種類である．
番号 $3$ の特産品は存在しないことに注意せよ．

入力例 2

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

出力例 2

この入力例は小課題 $2$ の制約を満たす．

入力例 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

出力例 3

この入力例は小課題 $3$ の制約を満たす．

入力例 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

出力例 4

1070 - 珍しい都市 (Unique Cities)

問題

入力

出力

制約

小課題