Connecting Universities
题意翻译
树之王国是一个由n-1条双向路连接着n个城镇的国家,任意两个城镇间都是联通的。
在树之王国共有2k所大学坐落于不同的城镇之中。
最近,树国总统颁布了一项在大学间建立高速信息网络的法案。教育部部长以他自己的方式理解了这项法案,他发现用电缆连接各所学校是绰绰有余的。形式上来说,这项法案安排的任务的确被完成了!(贪官...)
为了能尽可能多地获取财政预算,部长打算把大学分成一对一对的,使得在各所学校间建立连接所需的电缆最长。换句话说,k对大学间的距离总和越大越好。
帮助部长完成这个任务。当然了,每所大学不能重复出现在多对里。你可以认为每条路的长度均为1。
输入格式:
输入数据的第一行包括两个整数n和k(2<=n<=200000,1<=k<=n/2),分别表示城镇的数量以及大学数量的一半。你可以认为城镇是从1到n编号的。
第二行包括2k个整数u1,u2,...,u2k(1<=ui<=n),表示第i所大学所在城镇编号。
接下来的n-1行中每行都包括两个整数xj,yj(1<=xj,yj<=n),表示第j条道路连接着xj与yj两座城镇。左右的道路都是双向道路。你只能使用这些道路移动。
输出格式:
输出k对大学间最大的距离总和。
说明:
下图展示了在样例一的一种可能的结果。如果你把坐落于1号城镇的大学和坐落于6号城镇的大学连接在一起,把坐落于2号城镇的大学和坐落于5号城镇的大学连接在一起,那么距离总和为6,在样例一中是最大距离总和。
![pic](https://cdn.luogu.org/upload/vjudge_pic/CF700B/d24b24140d15e90d634b3c0f9f8b570ac75746f9.png)
题目描述
Treeland is a country in which there are $ n $ towns connected by $ n-1 $ two-way road such that it's possible to get from any town to any other town.
In Treeland there are $ 2k $ universities which are located in different towns.
Recently, the president signed the decree to connect universities by high-speed network.The Ministry of Education understood the decree in its own way and decided that it was enough to connect each university with another one by using a cable. Formally, the decree will be done!
To have the maximum sum in the budget, the Ministry decided to divide universities into pairs so that the total length of the required cable will be maximum. In other words, the total distance between universities in $ k $ pairs should be as large as possible.
Help the Ministry to find the maximum total distance. Of course, each university should be present in only one pair. Consider that all roads have the same length which is equal to $ 1 $ .
输入输出格式
输入格式
The first line of the input contains two integers $ n $ and $ k $ ( $ 2<=n<=200000 $ , $ 1<=k<=n/2 $ ) — the number of towns in Treeland and the number of university pairs. Consider that towns are numbered from $ 1 $ to $ n $ .
The second line contains $ 2k $ distinct integers $ u_{1},u_{2},...,u_{2k} $ ( $ 1<=u_{i}<=n $ ) — indices of towns in which universities are located.
The next $ n-1 $ line contains the description of roads. Each line contains the pair of integers $ x_{j} $ and $ y_{j} $ ( $ 1<=x_{j},y_{j}<=n $ ), which means that the $ j $ -th road connects towns $ x_{j} $ and $ y_{j} $ . All of them are two-way roads. You can move from any town to any other using only these roads.
输出格式
Print the maximum possible sum of distances in the division of universities into $ k $ pairs.
输入输出样例
输入样例 #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
说明
The figure below shows one of possible division into pairs in the first test. If you connect universities number $ 1 $ and $ 6 $ (marked in red) and universities number $ 2 $ and $ 5 $ (marked in blue) by using the cable, the total distance will equal $ 6 $ which will be the maximum sum in this example.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF700B/d24b24140d15e90d634b3c0f9f8b570ac75746f9.png)