题目描述

题目译自 JOISC 2019 Day4 T2「合併 / Mergers」

JOI 合众国有 $N$ 个城市，编号为 $1 \ldots N$，并且有 $N-1$ 条高速公路，编号为 $1 \ldots N-1$。第 $i$ $(1 \le i \le N-1)$ 条高速公路双向连接城市 $A_i$ 与 $B_i$。一个人可以利用高速公路从任意一个城市到达另一个城市。

目前，JOI 合众国有 $K$ 个州，编号为 $1 \ldots K$，城市 $j$ $(1 \le j \le N)$ 属于州 $S_j$。任意一个州内至少有一个城市。

JOI 合众国总统 K 先生害怕国家会分裂。JOI 合众国被称作可分裂的当且仅当所有城市可以被划分为 $X$ 组和 $Y$ 组，并且满足以下条件：

• 所有城市属于 $X$ 组或 $Y$ 组之一；
• $X$ 组中至少有一个城市；
• $Y$ 组中至少有一个城市；
• 对于任意一个州，所有所属州相同的城市都在同一组；
• 一个人可以从 $X$ 组的任意一个城市出发，通过高速公路并只经过属于 $X$ 组的城市到达 $X$ 组的任意一个城市；
• 一个人可以从 $Y$ 组的任意一个城市出发，通过高速公路并只经过属于 $Y$ 组的城市到达 $Y$ 组的任意一个城市。

K 先生将要合并一些州，使得 JOI 合众国是不可分裂的。当他合并州的时候，他会选择两个州，然后把这两个州合并成一个新州。新州下辖的城市为原来两个州所有下辖的城市。K 先生想要在合并次数最少的情况下完成合并任务，使得 JOI 合众国是不可分裂的。

注意，如果 JOI 合众国只有一个州，那么它是不可分裂的。

写一个程序，在给定所有城市，州和高速公路的信息的情况下，计算使得 JOI 合众国不可分裂的最小合并次数。

---

输入格式

从标准输入读入以下数据：

• 第一行两个正整数 $N$, $K$，表示 JOI 合众国有 $N$ 个城市 $K$ 个州；
• 接下来 $N-1$ 行，每行两个整数 $A_i$, $B_i$，描述 JOI 合众国内部高速公路的情况；
• 接下来 $N$ 行，每行一个正整数 $S_j$，表示 $j$ 号城市属于 $S_j$ 州。

---

输出格式

输出一个整数到标准输出，表示使得 JOI 合众国不可分裂的最小合并次数。

---

样例 1

输入

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

输出

1

在这组样例中，初始情况的 JOI 合众国是可分裂的，例如，如果将 $1,2,3,4$ 号城市分到 $X$ 组，$5$ 号城市分到 $Y$ 组，这样是满足可分裂的条件的。

如果 K 先生将 $3$, $4$ 号州合并为一个州，JOI 合众国就不可分裂了，因此答案为 $1$。

---

样例 2

输入

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

输出

0

在这组样例中，初始情况 JOI 合众国就不可分裂，因此答案是 $0$。

---

样例 3

输入

2 2
1 2
1
2

输出

1

---

数据范围与提示

对于全部数据，$1 \le N \le 5 \times 10^5$, $1 \le K \le N$, $1 \le A_i,B_i \le N$, $1 \le S_j \le K$，保证利用高速公路可以从任意一个城市到达另一个城市，对于任意 $k$ $(1 \le k \le K)$，都存在 $j$ $(1 \le j \le N)$ 使得 $S_j = k$。

详细子任务及附加条件如下表：

子任务	附加条件	分值
1	$N \le 100$, $K \le 7$	10
2	$N \le 3 \times 10^3$	24
3	$N \le 10^5$, $K \le 50$	14
4	$N \le 10^5$，在初始情况，同一个州下辖的城市之间最多只需要经过 $100$ 条高速公路就可以互相到达。	22
5	无附加条件	30

---