Connecting Universities
Contest: Codeforces Round 364 (Div. 1)
Difficulty rating: 1800
Tags: dfs and similar, dp, graphs, trees

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 format:
The first line of the input contains two integers n and k (2 ≤ n ≤ 200 000, 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 format:
Print the maximum possible sum of distances in the division of universities into k pairs.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
7 2
1 5 6 2
1 3
3 2
4 5
3 7
4 3
4 6

Example output:
6

Example 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

Example output:
9

Editorial:
Let's root a tree with vertex 1 by single DFS and by the way find two values for every vertex v:
• lv — length of the edge that leads from parent of v to vertex v;
• sv — the number of universities in the subtree of vertex v (including v itself).
Consider any optimal solution, i.e. such solution that the total length is maximum. Look at some edge that leads from the parent of v to v. We claim that it should be used in min(sv, 2·k - sv) paths. It obviously cannot be used more time than this value, however, if it is used less number of times, that means there is at least one connected pair (let's say a and b) located in the subtree of v and at least one connected pair located outside (vertices c and d). By the properties of the tree, paths from a to c and from b to d cover all edges of the paths from a to b and from c to d plus some extra edges, meaning the current answer is not optimal. Thus, this edge will be used exactly min(sv, 2·k - sv) times.
The above means we can compute the answer value as $$\sum_{v \in V} \min(s_v, 2 \cdot k - s_v)$$. Note that the above method doesn't provide the optimal matching itself (though, not many modifications required).