AT_joisc2019_k 合併 (Mergers)

题目译自 [JOISC 2019](https://www.ioi-jp.org/camp/2019/2019-sp-tasks/index.html) Day4 T2「[合併](https://www.ioi-jp.org/camp/2019/2019-sp-tasks/day4/mergers.pdf) / [Mergers](https://www.ioi-jp.org/camp/2019/2019-sp-tasks/day4/mergers-en.pdf)」

JOI 合众国有 $N$ 个城市，编号为 $1\dots N$，并且有 $N−1$ 条高速公路，编号为 $1\dots N−1$。第 $i (1\le i\le N−1)$ 条高速公路双向连接城市 $A_i$ 与 $B_i$。一个人可以利用高速公路从任意一个城市到达另一个城市。 目前，JOI 合众国有 $K$ 个州，编号为 $1\dots K$，城市 $j (1\le j\le N)$ 属于州 $S_j$。任意一个州内至少有一个城市。 JOI 合众国总统 K 先生害怕国家会分裂。JOI 合众国被称作**可分裂的**当且仅当所有城市可以被划分为 $\texttt X$ 组和 $\texttt Y$ 组，并且满足以下条件： - 所有城市属于 $\texttt X$ 组或 $\texttt Y$ 组之一； - $\texttt X$ 组中至少有一个城市； - $\texttt Y$ 组中至少有一个城市； - 对于任意一个州，所有所属州相同的城市都在同一组； - 一个人可以从 $\texttt X$ 组的任意一个城市出发，通过高速公路且只经过 $\texttt X$ 组的城市到达 $\texttt X$ 组的任意一个城市； - 一个人可以从 $\texttt Y$ 组的任意一个城市出发，通过高速公路且只经过 $\texttt Y$ 组的城市到达 $\texttt Y$ 组的任意一个城市。 K 先生将要合并一些州，使得 JOI 合众国是不可分裂的。当他合并州的时候，他会选择两个州，然后把这两个州合并成一个新州。新州下辖的城市为原来两个州所有下辖的城市。K 先生想要在合并次数最少的情况下完成合并任务，使得 JOI 合众国是不可分裂的。 注意，如果 JOI 合众国只有一个州，那么它是不可分裂的。 写一个程序，在给定所有城市，州和高速公路的信息的情况下，计算使得 JOI 合众国不可分裂的最小合并次数。

第一行两个正整数 $N,K$，表示城市数量和洲的数量。 接下来 $N-1$ 行每行两个正整数 $A_i,B_i$，表示一条高速公路。 接下来 $N$ 行每行一个数 $S_j$，表示第 $j$ 个城市属于第 $S_j$ 个洲。

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

## 输入输出样例 ### 样例输入 #1 ``` 5 4 1 2 2 3 3 4 3 5 1 2 1 3 4 ``` ### 样例输出 #1 ``` 1 ``` ### 样例输入 #2 ``` 5 4 1 2 2 3 3 4 4 5 1 2 3 4 1 ``` ### 样例输出 #2 ``` 0 ``` #### 样例输入 #3 ``` 2 2 1 2 1 2 ``` #### 样例输出 #3 ``` 1 ``` ## 说明/提示 **【样例解释】** 对于第一组样例，最初国家是可分裂的。例如，将城市 $1,2,3,4$ 归为 $\texttt X$ 组，将城市 $5$ 归为 $\texttt Y$ 组。如果将第 $3$ 个洲和第 $4$ 个洲合并，国家就会变得不可分裂。因此答案是 $1$。 对于第二组样例，最初国家是不可分裂。因此答案是 $0$。 **【数据范围】** 对于 $100\%$ 的数据，$1\le N\le 5\times 10^5,1\le K,A_i,B_i\le N,1\le S_i\le K$。