P14350 [JOISC 2019] 合并 / Mergers

JOI 国有 $N$ 个城市，编号从 $1$ 到 $N$，以及 $N-1$ 条高速公路，编号从 $1$ 到 $N-1$。第 $i$ 条高速公路（$1 \le i \le N-1$）双向连接城市 $A_i$ 与城市 $B_i$。人们可以通过高速公路在任意两个城市之间通行。 目前，JOI 国由 $K$ 个州组成，编号从 $1$ 到 $K$。城市 $j$（$1 \le j \le N$）属于州 $S_j$。每个州至少包含一个城市。 JOI 国总统 Mr. K 担心国家分裂。若能将所有城市划分为 Group X 与 Group Y，且满足以下条件，则称 JOI 国是 **可分的**： - 任意城市属于 Group X 或 Group Y 之一。 - Group X 至少包含一个城市。 - Group Y 至少包含一个城市。 - 对于任意一个州，该州内所有城市必须属于同一个组。 - 仅通过 Group X 内的城市，可以在 Group X 内的任意两个城市之间通行。 - 仅通过 Group Y 内的城市，可以在 Group Y 内的任意两个城市之间通行。 Mr. K 计划通过合并州来使 JOI 国不可分。当他合并州时，他选择两个州并将它们合并为一个州；合并后的州包含这两个州的所有城市。Mr. K 希望通过尽可能少的合并次数，使 JOI 国变得不可分。 请注意，若 JOI 国仅剩一个州，则该国不可分。 请编写一个程序，给定城市、高速公路和州的信息，计算使 JOI 国不可分所需的最少合并次数。

从标准输入读取以下数据。输入中的所有值均为整数。 $N$ $K$ $A_1$ $B_1$ $\vdots$ $A_{N-1}$ $B_{N-1}$ $S_1$ $\vdots$ $S_N$

向标准输出写入一个整数，表示使 JOI 国不可分所需的最少合并次数。

### 限制条件 - $1 \le N \le 500\,000$。 - $1 \le K \le N$。 - $1 \le A_i \le N$（$1 \le i \le N-1$）。 - $1 \le B_i \le N$（$1 \le i \le N-1$）。 - 任意两个城市之间均可通过高速公路通行。 - $1 \le S_j \le K$（$1 \le j \le N$）。 - 对于任意 $k$（$1 \le k \le K$），存在某个 $j$（$1 \le j \le N$）使得 $S_j = k$。 ### 子任务 1. （10 分）$N \le 100$，$K \le 7$。 2. （24 分）$N \le 3\,000$。 3. （14 分）$N \le 100\,000$，$K \le 50$。 4. （22 分）$N \le 100\,000$。初始状态下，同一州内的任意两个城市之间最多可通过 100 条高速公路通行。 5. （30 分）无额外限制。 翻译由 Qwen3-235B 完成