레이팅 미적용JOI 国にはN 個の都市があり,1 からN までの番号がついている.これらの都市はN −1 本の道路で結
ばれている.i 番目(1 ≦i ≦N −1) の道路は都市Ai と都市Bi を結んでおり,双方向に通行可能である.ど
の都市からどの都市へも何本かの道路を通行することで移動できる.
JOI 国にはいくつかの特産品が存在する.特産品には,種類を表す1 以上M 以下の番号が付けられてい
る(JOI 国で生産されている特産品に対応していない番号があるかもしれない).各都市は1 つの特産品を
生産しており,都市j (1 ≦j ≦N) では特産品C j を生産している.複数の都市が同じ種類の特産品を生産
することがあるかもしれない.
2 つの都市の間の距離は,その間を移動するために通る道路の本数の最小値である.都市x (1 ≦x ≦N)
から見て都市y (1 ≦y ≦N, y , x) が珍しい都市であるとは,すべての都市z (1 ≦z ≦N, z , x, z , y) につい
て,都市x, y 間の距離と都市x, z 間の距離が異なることを意味する.
JOI 国の大臣であるK 理事長は,すべてのj (1 ≦j ≦N) について,都市j から見て珍しい都市で生産さ
れている特産品が何種類あるかを知りたい.
JOI 国の道路の情報と,各都市で生産されている特産品の番号が与えられたとき,各都市ごとに,その
都市から見て珍しい都市で生産されている特産品が何種類あるかを求めるプログラムを作成せよ.
• 2 ≦N ≦200 000.
• 1 ≦M ≦N.
第18 回日本情報オリンピック(JOI 2018/2019) 本選
2019 年2 月10 日(茨城県つくば市)
• 1 ≦Ai ≦N (1 ≦i ≦N −1),1 ≦Bi ≦N (1 ≦i ≦N −1).
• Ai , Bi (1 ≦i ≦N −1).
• どの都市からどの都市へも何本かの道路を通行することで移動できる.
• 1 ≦C j ≦M (1 ≦j ≦N).
- (4 点) N ≦2 000.
- (32 点) M = 1.
- (32 点) M = N,C j = j (1 ≦j ≦N).
- (32 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N M
A1 B1
...
AN−1 BN−1
C1 · · · CN
標準出力にN 行で出力せよ.j 行目(1 ≦j ≦N) には,都市j から見て珍しい都市で生産されている特産
品が何種類あるかを出力せよ.
5 4
1 2
2 3
3 4
3 5
1 2 1 2 4
2
0
1
1
1
7 1
1 2
2 3
3 4
4 5
5 6
6 7
1 1 1 1 1 1 1
1
1
1
0
1
1
1
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
4
3
4
2
0
2
2
0
3
2
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
2
0
1
1
1
1
1
0
0
1
2
0
1
1
2
0
2
1
2
3
0
0