#3014. 「JOI 2019 Final」独特的城市

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 JOI 2019 Final T5「珍しい都市 / Unique Cities

JOI 国有 N 个城市,城市从 1 N 编号。这些城市被 N-1 条双向道路连接,第 i 条路连接两个城市 A_i B_i 。从任何城市出发,可以到达所有城市。

JOI 国有些特产,每种特产的编号都在 1 M 之间(包括 1 M ),但是 1 M 的某些整数可能不代表 JOI 国的特产。JOI 国的每个城市都产一种特产。 j 城产的特产是 C_j 。多个城市可能产相同的特产。

我们定义两个城市之间的距离为从一个城市到另一个城市需要经过的最少道路数,对于城市 x\ (1\le x\le N) ,我们定义城市 y\ (1\le y\le N,y\neq x) 独特的城市当且仅当对于任何一个城市 z\ (1\le z\le N,z\neq x,z\neq y) x y 间的距离不等于 x z 之间的距离。

JOI 国交通部部长 K 先生想知道对于城市 j\ (1\le j\le N) 独特的城市一共能产多少种特产。

给出 JOI 国的道路信息与每个城市产的特产,写一个程序计算对于每个城市的独特的城市,一共能产多少种特产。

输入格式

第一行两个整数 N,M ,意义如题目描述。

接下来 N-1 行,每行两个整数 A_i,B_i ,意义如题目描述。

最后一行 N 个正整数,第 j 个为 C_j ,意义如题目描述。

输出格式

输出 N 行,第 j\ (1\le j\le N) 行表示对于城市 j\ (1\le j\le N) 独特的城市一共能产多少种特产。

样例

样例输入 1

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

样例输出 1

2
0
1
1
1

样例说明 1

对于城市 1 ,它的独特城市是城市 2,3 ,城市 2 产特产 2 ,城市 3 产特产 1 ,一共产两种特产,因此答案是 2
对于城市 2 ,没有独特城市,因此输出 0
对于城市 3 ,它的独特城市是城市 1 ,城市 1 产特产 1 ,因此答案是 1
对于城市 4 ,它的独特城市是城市 1,3 ,城市 1 产特产 1 ,城市 3 产特产 1 ,一共产一种特产,因此答案是 1
对于城市 5 ,它的独特城市是城市 1,3 ,城市 1 产特产 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

本组样例符合子任务 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

本组样例符合子任务 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

数据范围与提示

对于全部数据, 1\le N\le 2\times 10^5,1\le M\le N,1\le A_i,B_i\le N\ (A_i\neq B_i,1\le i\le N-1),1\le C_j\le M\ (1\le j\le M) ,并且保证从一个城市永远可以通过道路到达任何一个城市。

详细子任务及附加限制如下表:

Subtask 附加限制 分值
1 N\le 2000 4
2 M=1 32
3 M=N,C_j=j\ (1\le j\le N)  32 
4 32