ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4636: Connecting Universities

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：4 通过：3
提交提交记录统计Web Board

题目描述

B. Connecting Universities


B.连接大学

每次测试的时间限制

3秒

每次测试的内存限制

256字节

输入

标准输入

输出

标准输出

Treeland是一个国家，有n个城镇，由n-1条双向公路连接，这样就可以从任何一个城镇到任何另一个城镇。

在树地有2k所大学，它们位于不同的城镇。

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

教育部为了使预算达到最大限度，决定将大学分成两组，使光缆的总长度达到最大限度。换句话说，k对大学之间的总距离应该尽可能大。

帮助魔法部找到最大总距离。当然，每所大学只能参加一对。假设所有道路的长度都等于1。

输入

输入的第一行包含两个整数n和k(2≤n≤200000,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对的最大可能距离之和。

例子

 

time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.
Input
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 u1,u2,...,u2k (1≤ui≤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 xj and yj (1≤xj,yj≤n), which means that the j-th road connects towns xj and yj. All of them are two-way roads. You can move from any town to any other using only these roads.
Output
Print the maximum possible sum of distances in the division of universities into k pairs.
Examples
Input 
7 2
1 5 6 2
1 3
3 2
4 5
3 7
4 3
4 6
Output 
6
Input 
9 3
3 2 1 6 5 9
8 9
3 2
2 7
3 4
7 6
4 5
2 1
2 8
Output 
9
Note
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.

输入样例 复制

输出样例 复制

分类标签