#3280. 「JOISC 2020 Day4」首都城市

内存限制:512 MiB 时间限制:2500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ShineEternal

题目描述

题目译自 JOISC 2020 Day4 T1「首都 / Capital City

在 JOI 的国度有 N 个小镇,从 1 N 编号,并由 N-1 条双向道路连接。第 i 条道路连接了 A_i B_i 这两个编号的小镇。

这个国家的国王现将整个国家分为 K 个城市,从 1 K 编号,每个城市都有附属的小镇,其中编号为 j 的小镇属于编号为 C_j 的城市。每个城市至少有一个附属小镇。

国王还要选定一个首都。首都的条件是该城市的任意小镇都只能通过属于该城市的小镇到达。

但是现在可能不存在这样的选址,所以国王还需要将一些城市进行合并。对于合并城市 x y ,指的是将所有属于 y 的小镇划归给 x 城。

你需要求出最少的合并次数。

输入格式

输入第一行两个整数 N,K ,为小镇和城市的数量。

接下来的 N-1 行,每行两个整数 A_i,B_i ,描述了 N-1 条道路。

再接下来的 N 行,每行一个整数 C_j ,表示编号为 j 的小镇属于编号为 C_j 的城市。

输出格式

输出一行一个整数为最少的合并次数。

样例

样例输入 1

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

样例输出 1

1

样例说明 1

你可以对城市 1 3 进行合并,然后选定 1 为首都,因为最初任何城市都无法作为首都。总花费为 1

这个样例满足子任务 1,2,4

样例输入 2

8 4
4 1
1 3
3 6
6 7
7 2
2 5
5 8
2
4
3
1
1
2
3
4

样例输出 2

1

样例说明 2

这个样例满足子任务 1,2,3,4

样例输入 3

12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4

样例输出 3

2

样例说明 3

这个样例满足子任务 1,2,4

数据范围与提示

对于 100\% 的数据, 1\leq N\leq 2\times 10^5 ,保证:

  • 1\leq K\leq N

  • 1\leq A_i,B_i\leq N(1\leq i\leq N-1)

  • 从任何一个小镇出发都能到达其他任何小镇;

  • 1\leq C_j\leq K(1\leq j\leq N)

  • 对于每一个 k(1\leq k\leq K) ,存在一个 j(1\leq j\leq N) ,使得 C_j=k

详细子任务及附加限制如下表所示:

子任务编号 附加限制 分值
1 N\leq 20 1
2 N\leq 2000 10
3 每个小镇最多可通过公路与两个小镇直接相连 30
4 无附加限制 59