CF700B Connecting Universities

题目描述

树之王国是一个由 $ n-1 $ 条双向路连接着 $ n $ 个城镇的国家,任意两个城镇间都是联通的。 在树之王国共有 $ 2k $ 所大学坐落于不同的城镇之中。 最近,树国总统颁布了一项在大学间建立高速信息网络的法案。教育部部长以他自己的方式理解了这项法案,他发现用电缆连接各所学校是绰绰有余的。形式上来说,这项法案安排的任务的确被完成了! 为了能尽可能多地获取财政预算,部长打算把大学分成一对一对的,使得在各所学校间建立连接所需的电缆最长。换句话说,$ k $ 对大学间的距离总和越大越好。 帮助部长完成这个任务。当然了,每所大学不能重复出现在多对里。你可以认为每条路的长度均为 $ 1 $。

输入格式

输入数据的第一行包括两个整数 $ n $ 和 $ k $($ 2 \le n \le 200000 $,$ 1 \le k \le \frac{n}{2} $),分别表示城镇的数量以及大学数量的一半。你可以认为城镇是从 $ 1 $ 到 $ n $ 编号的。 第二行包括 $ 2k $ 个整数 $ u_{1},u_{2},...,u_{2k} $($ 1 \le u_{i} \le n $),表示第 $ i $ 所大学所在城镇编号。 接下来的 $ n-1 $ 行中每行都包括两个整数 $ x_{j},y_{j} $($ 1 \le x_{j},y_{j} \le n $),表示第 $ j $ 条道路连接着 $ x_{j} $ 与 $ y_{j} $ 两座城镇。左右的道路都是双向道路。你只能使用这些道路移动。

输出格式

输出 $ k $ 对大学间最大的距离总和。

说明/提示

下图展示了在样例一的一种可能的结果。如果你把坐落于 $ 1 $ 号城镇的大学和坐落于 $ 6 $ 号城镇的大学连接在一起,把坐落于 $ 2 $ 号城镇的大学和坐落于 $ 5 $ 号城镇的大学连接在一起,那么距离总和为 $ 6 $,在样例一中是最大距离总和。 ![pic](https://cdn.luogu.org/upload/vjudge_pic/CF700B/d24b24140d15e90d634b3c0f9f8b570ac75746f9.png)