题目描述

译自 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)$ 的独特的城市一共能产多少种特产。

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\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)$，并且保证从一个城市永远可以通过道路到达任何一个城市。

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