AT_joisc2020_j.首都 (Capital City)

JOI 国拥有 $N$ 个城镇，编号为 $1$ 到 $N$，这些城镇由 $N-1$ 条双向道路连接。

JOI 国还拥有 $K$ 个城市，编号为 $1$ 到 $K$，第 $i$ 个城镇属于第 $C_i$ 个城市。

现在 JOI 国的总理 JOI 君 114514 世要挑选一个城市作为首都，从首都中的任一个城镇到达另一个首都中的城镇可以只经过首都中的城镇，但这明显是不合理的。

所以 JOI 君 114514 世要进行合并城市，合并城市 $x$ 和城市 $y$ 就会把城市 $y$ 里的所有小镇归为城市 $x$。

求能找到首都的最小合并次数。

第一行两个整数 $N,K$ 代表城镇数和城市数。
接下来 $N-1$ 行每行两个整数 $u,v$ 代表一条双向边。
接下来 $N$ 行第 $i$ 行一个整数 $C_i$ 代表第 $i$ 个城镇属于第 $C_i$ 个城市。

一行一个整数代表最小的合并次数。

样例 #1

样例输入 #1

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

样例输出 #1

1

样例 #2

样例输入 #2

8 4
4 1
1 3
3 6
6 7
7 2
2 5
5 8
2
4
3
1
1
2
3
4

样例输出 #2

1

样例 #3

样例输入 #3

12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4

样例输出 #3

2

样例 1 解释

可以将城市 $1$ 和 $3$ 合并，然后选择城市 $1$ 作为首都。

子任务

子任务	特殊性质	分数
$1$	$N \le 20$	$1$
$2$	$N \le 2000$	$10$
$3$	每个城镇最多与两个城镇相连	$30$
$4$	无	$59$

对于 $100\%$ 的数据，$1 \le K,u,v \le N \le 2 \times 10^5$，保证从任何一个城镇出发都能到达其他城镇，$1 \le C_i \le K$。

翻译自 第１９回日本情報オリンピック　春季トレーニング合宿 Day4 A 首都。