题目背景

某岛国交通部门正在整理一份各城市的「独特度」档案,需要你帮忙写一个统计程序。

题目描述

这个岛国共有 $N$ 座城市,编号从 $1$ 到 $N$。这些城市之间由 $N-1$ 条双向公路相连,其中第 $i$ 条公路连接城市 $A_i$ 与城市 $B_i$。从任意一座城市出发,都能经由公路到达其他所有城市。

岛国有若干种特产,每种特产用 $1$ 到 $M$ 之间的一个整数编号($1$ 到 $M$ 中的某些整数可能并不对应任何特产)。每座城市都出产恰好一种特产,城市 $j$ 出产的特产编号为 $C_j$;不同的城市可能出产同一种特产。

把两座城市之间至少要经过的公路条数称为它们之间的距离。对于城市 $x$,如果城市 $y$($y\neq x$)满足:不存在另一座城市 $z$($z\neq x,z\neq y$),使得 $x$ 到 $z$ 的距离等于 $x$ 到 $y$ 的距离,那么就称 $y$ 是城市 $x$ 的一座独一无二的城市(换句话说,在与 $x$ 距离相同的所有城市里,$y$ 是唯一的一座)。

交通部门想知道:对于每一座城市,它的所有独一无二的城市一共出产多少种不同的特产。给定公路连接信息与每座城市的特产编号,请你编写程序回答这个问题。

输入格式

第一行两个整数 $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$ 与特产 $1$,共 $2$ 种,因此答案是 $2$;

对于城市 $2$,没有独一无二的城市,因此输出 $0$;

对于城市 $3$,独一无二的城市是 $1$ 号,出产特产 $1$,因此答案是 $1$;

对于城市 $4$,独一无二的城市是 $1$ 号和 $3$ 号,它们都出产特产 $1$,因此答案是 $1$;

对于城市 $5$,独一无二的城市是 $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 \le N$,$A_i,B_i \le N$,$A_i \neq B_i$,$1\le C_j \le M$。