题目描述

题目译自 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 合众国不可分裂的最小合并次数。

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 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$。

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