题目描述

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 国不可分所需的最少合并次数。

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

1

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

0

2 2
1 2
1
2

1

提示

限制条件

• $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 完成