← 返回题目列表

AtCoder · joi2019ho_e

E. 独特的城市

中文机器翻译题面 查看原题

配点: 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
\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 点)没有额外的限制。

入力例 1

5 4
1 2
2 3
3 4
3 5
1 2 1 2 4

出力例 1

2
0
1
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

1
1
1
0
1
1
1

此输入示例是一个小作业。 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

4
3
4
2
0
2
2
0
3
2

此输入示例是一个小作业。 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

2
0
1
1
1
1
1
0
0
1
2
0
1
1
2
0
2
1
2
3
0
0