← 返回题目列表

Codeforces · 700/B

B. 连接大学

中文机器翻译题面 查看原题

Treeland 是一个国家,其中有 n 个城镇,由 n - 1 条双向道路连接,因此可以从任何城镇到达任何其他城镇。

Treeland 有 2k 所大学,分布在不同的城镇。

最近,总统签署了通过高速网络连接大学的法令。教育部以自己的方式理解该法令,并决定使用电缆将每所大学与另一所大学连接起来就足够了。正式地,法令将执行!

为了在预算中获得最大数额,该部决定将大学分成两对,以使所需电缆的总长度达到最大。换句话说,k对大学之间的总距离应该尽可能大。

帮助部找到最大总距离。当然,每所大学应该只出现一对。考虑所有道路的长度相同,都等于 1。

输入

输入的第一行包含两个整数 n 和 k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ n / 2) - Treeland 中城镇的数量和大学对的数量。考虑城镇的编号为 1 到 n。

第二行包含 2k 个不同的整数 u1, u2, ..., u2k (1 ≤ ui ≤ n) - 大学所在城镇的索引。

接下来的 n - 1 行包含道路的描述。每行包含一对整数 xj 和 yj (1 ≤ xj, yj ≤ n),这意味着第 j 条路连接城镇 xj 和 yj。全部都是双向路。您可以仅使用这些道路从任何城镇移动到任何其他城镇。

输出

打印将大学划分为 k 对的最大可能距离总和。

示例

输入 #1

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

输出 #1

6

输入 #2

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

输出 #2

9

注意

下图显示了第一个测试中可能的成对分组。如果使用电缆连接 1 号和 6 号大学(以红色标记)以及 2 号和 5 号大学(以蓝色标记),则总距离将等于 6,这将是本例中的最大总和。