AT_joi2019ho_e 珍しい都市 (Unique Cities)

[problemUrl]: https://atcoder.jp/contests/joi2019ho/tasks/joi2019ho_e 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 $ 点) 追加の制約はない． - - - - - - ### Sample Explanation 1 都市 $ 1 $ から見て珍しい都市は都市 $ 2,\ 3 $ であり，そこで生産される特産品は特産品 $ 2,\ 1 $ なので，答えは $ 2 $種類である． 都市 $ 2 $ から見て珍しい都市は存在しないので，答えは $ 0 $ 種類である． 都市 $ 3 $ から見て珍しい都市は都市 $ 1 $ であり，そこで生産される特産品は特産品 $ 1 $ なので，答えは $ 1 $ 種類である． 都市 $ 4 $ から見て珍しい都市は都市 $ 1,\ 3 $ であり，どちらの都市においても生産される特産品は特産品 $ 1 $ なので，答えは $ 1 $ 種類である． 都市 $ 5 $ から見て珍しい都市は都市 $ 1,\ 3 $ であり，どちらの都市においても生産される特産品は特産品 $ 1 $ なので，答えは $ 1 $ 種類である． 番号 $ 3 $ の特産品は存在しないことに注意せよ． - - - - - - ### Sample Explanation 2 この入力例は小課題 $ 2 $ の制約を満たす． - - - - - - ### Sample Explanation 3 この入力例は小課題 $ 3 $ の制約を満たす． - - - - - -