题目描述

题目译自 JOISC 2020 Day4 T1「首都 / Capital City」

在 JOI 的国度有 $N$ 个小镇，从 $1$ 到 $N$ 编号，并由 $N-1$ 条双向道路连接。第 $i$ 条道路连接了 $A_i$ 和 $B_i$ 这两个编号的小镇。

这个国家的国王现将整个国家分为 $K$ 个城市，从 $1$ 到 $K$ 编号，每个城市都有附属的小镇，其中编号为 $j$ 的小镇属于编号为 $C_j$ 的城市。每个城市至少有一个附属小镇。

国王还要选定一个首都。首都的条件是该城市的任意小镇都只能通过属于该城市的小镇到达。

但是现在可能不存在这样的选址，所以国王还需要将一些城市进行合并。对于合并城市 $x$ 和 $y$ ，指的是将所有属于 $y$ 的小镇划归给 $x$ 城。

你需要求出最少的合并次数。

输入格式

输入第一行两个整数 $N,K$，为小镇和城市的数量。

接下来的 $N-1$ 行，每行两个整数 $A_i,B_i$，描述了 $N-1$ 条道路。

再接下来的 $N$ 行，每行一个整数 $C_j$，表示编号为 $j$ 的小镇属于编号为 $C_j$ 的城市。

输出格式

输出一行一个整数为最少的合并次数。

样例 1

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

1

你可以对城市 $1$ 和 $3$ 进行合并，然后选定 $1$ 为首都，因为最初任何城市都无法作为首都。总花费为 $1$ 。

这个样例满足子任务 $1,2,4$。

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

1

这个样例满足子任务 $1,2,3,4$。

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

2

这个样例满足子任务 $1,2,4$。

数据范围与提示

对于 $100\%$ 的数据，$1\leq N\leq 2\times 10^5$，保证：

• $1\leq K\leq N$；

• $1\leq A_i,B_i\leq N(1\leq i\leq N-1)$；

• 从任何一个小镇出发都能到达其他任何小镇；

• $1\leq C_j\leq K(1\leq j\leq N)$；

• 对于每一个 $k(1\leq k\leq K)$，存在一个 $j(1\leq j\leq N)$，使得 $C_j=k$。

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