珍しい都市 (Unique Cities)

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\)
\(\vdots\)
\(A_{N-1}\) \(B_{N-1}\)
\(C_1\) \(\cdots\) \(C_N\)

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

• \(2 \leqq N \leqq 200\,000\)．
• \(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 , B_i (1 \leqq i \leqq N - 1\))．
• どの都市からどの都市へも何本かの道路を通行することで移動できる．
• \(1 \leqq C_j \leqq M\) (\(1 \leqq j \leqq N\))．

1. (\(4\) 点) \(N \leqq 2\,000\)．
2. (\(32\) 点) \(M = 1\)．
3. (\(32\) 点) \(M = N\)，\(C_j = j\) (\(1 \leqq j \leqq N\))．
4. (\(32\) 点) 追加の制約はない．

JOI 2019 · JCIOI · CC BY-SA 4.0