#3040. 「JOISC 2019 Day4」合并

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

题目描述

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

样例

样例输入 1

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

样例输出 1

1

样例说明 1

在这组样例中,初始情况的 JOI 合众国是可分裂的,例如,如果将 1,2,3,4 号城市分到 X 组, 5 号城市分到 Y 组,这样是满足可分裂的条件的。

如果 K 先生将 3, 4 号州合并为一个州,JOI 合众国就不可分裂了,因此答案为 1

样例输入 2

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

样例输出 2

0

样例说明 2

在这组样例中,初始情况 JOI 合众国就不可分裂,因此答案是 0

样例输入 3

2 2
1 2
1
2

样例输出 3

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

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

子任务 附加条件 分值
1 N\le 100,K\le 7 10
2 N\le 3\times 10^3 24
3 N\le 10^5,K\le 50 14
4 N\le 10^5 ,在初始情况,同一个州下辖的城市之间最多只需要经过 100 条高速公路就可以互相到达。 22
5 无附加条件 30