背景

JOI 2019 Final T5

题目描述

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

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

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

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

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

输入格式

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

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

最后一行 $N$ 个正整数，第 $i$ 个为 $C_i$，意义如题目描述。

输出格式

输出 $N$ 行，第 $i$ 行表示对于城市 $i$ 的独特的城市一共能产多少种特产。

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

提示

样例解释 $1$：

对于城市 $1$，它的独特城市是城市 $2,3$，城市 $2$ 产特产 $2$，城市 $3$ 产特产 $3$，一共产两种特产，因此答案是 $2$；

对于城市 $2$，没有独特城市，因此输出 $0$；

对于城市 $3$，它的独特城市是城市 $1$，城市 $1$ 产特产 ，因此答案是 $1$；

对于城市 $4$，它的独特城市是城市 $1,3$，城市 $1,3$ 均产特产 $1$，因此答案是 $1$；

对于城市 $5$，它的独特城市是城市 $1,3$，城市 $1,3$ 均产特产 $1$，因此答案是 $1$。

注意：没有城市产特产 $3$。

对于 $4\%$ 的数据，$N\le 2000$。

另有 $32\%$ 的数据，$M=1$。

另有 $32\%$ 的数据，$M=N,C_j=j(1\le j \le N)$。

对于 $100\%$ 的数据，$1\le N \le 2\times 10^5,1\le M,A_i,B_i \le N,A_i \neq B_i,1\le C_j \le M$。