Treeland is a country in which there are n towns connected by n - 1 two-way road such…
- User
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 ≤ 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
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.
Assistant
We need to parse the problem: given a tree with n nodes, and 2k university nodes (distinct). We need to pair up the 2k nodes into k pairs to maximize sum of distances between paired nodes. The distance is the number of edges on the unique path. We need maximum total distance.
We have n up to 200k, so need O(n) or O(n log n).
We need to maximize sum of distances across k pairs. Equivalent to pairing 2k nodes to maximize sum of distances.
Observation: In tree, sum of distances over all pairs can be expressed in terms of edge contributions. For any edge, if we consider its removal splits tree into two components. For any pair of nodes (u,v), the edge lies on path if and only if u and v are in different components. So the contribution of that edge to the distance sum is the number of pairs that cross it.
Thus, total sum of distances = sum over edges (number of pairs where endpoints lie in opposite sides).
Now, for a given pairing (matching) of the 2k nodes, we consider each edge, and it contributes to total distance exactly if the two nodes of a pair are in different components of that edge. So for an edge, if we let X be the number of university nodes in one side (say left component) and Y = total - X on the other side. But careful: in a pairing, the contribution from that edge is the number of pairs that cross it, which is at most min(X, Y) but exactly? For a set of nodes, if we pair them arbitrarily, the number of cross-edge pairs equals ? Let's think: We have left side with A nodes, right side with B nodes, total 2k nodes (A+B=2k). We want to pair each left node with a right node possibly. The maximum number of pairs that can have one node in left and one in right is min(A, B). Actually, if we want to maximize the total number of crossing pairs, we would pair as many left-right as possible, but we are constrained by pairing all nodes. So we can have up to min(A, B) crossing pairs. But can we always achieve min(A, B)? Consider we have A and B. Suppose A <= B. Then we can pair each left node with a right node (so A crossing pairs). The remaining B - A right nodes must be paired among themselves, which yields non-crossing pairs. So yes, we can achieve exactly min(A, B) crossing pairs, and that's the maximum possible because each crossing pair uses one left node and one right node, so the number of crossing pairs cannot exceed min(A, B). So for each edge, the contribution to total distance is at most min(count_left, count_right) if we choose the pairing accordingly. And crucially, can we simultaneously achieve the maximum for all edges? For a tree, can we choose a pairing that simultaneously maximizes the crossing count for each edge? That would give total distance = sum over edges min(cnt_left, cnt_right). But is that achievable? This looks similar to: we have to pair up 2k nodes; the total distance is sum over edges of indicator that pair crosses edge. For each edge, we want as many crossing pairs as possible, but choices interact across edges because the pairing must be consistent.
This is reminiscent of problem "Maximum total distance by pairing nodes" often solved by considering that we can achieve sum over edges of min(subtree_uni_count, 2k - subtree_uni_count). That is, the maximum possible total distance equals sum over edges of min(S, 2k - S) where S is number of universities in the subtree (if we root arbitrarily). Let's test with examples.
First example: n=7, k=2, universities: 1,5,6,2. Tree edges: 1-3, 3-2, 4-5, 3-7, 4-3, 4-6. Wait they list edges: 1 3 3 2 4 5 3 7 4 3 4 6
That's a tree? Let's check: nodes 1-7. Edges: (1,3), (3,2), (4,5), (3,7), (4,3), (4,6). So connections: 3 connected to 1,2,7,4; 4 connected to 5,3,6. So tree indeed. Universities: 1,5,6,2. Let's root at 1 maybe? But we can compute for each edge the min. Let's compute number of universities in each side for each edge.
Edge (1-3): If cut, component containing 1 has universities {1}? Actually 1 is university, so count =1. Other side has universities {5,6,2} =3? Wait 2 is connected via 3, 5 and 6 via 4. So count =1 and 3. min=1.
Edge (3-2): Cut: component with 2 has university 2 (count=1). Other side has 3 universities (1,5,6). min=1.
Edge (4-5): component with 5 has university 5 (1). Other side has 3 universities (1,2,6). min=1.
Edge (3-7): component with 7 has none (0) and other side has 4. min=0.
Edge (4-3): cut separates {4,5,6} from {1,2,3,7}. Let's see: Edge between 4 and 3. If removed, component containing 4: nodes 4,5,6; universities: 5,6 -> count=2. Component containing 3: nodes 1,2,3,7; universities: 1,2 -> count=2. min=2.
Edge (4-6): component with 6 has university 6 (1), other side has 3? Actually other side: all except 6 => universities 1,2,5 =3. min=1.
Sum of mins = 1+1+1+0+2+1 = 6. Matches output 6. Good.
Second example: n=9, k=3, universities: 3,2,1,6,5,9. Edges: 8 9 3 2 2 7 3 4 7 6 4 5 2 1 2 8
We'll compute min per edge. But output is 9. Let's test.
First list edges: (8,9), (3,2), (2,7), (3,4), (7,6), (4,5), (2,1), (2,8).
Universities: 3,2,1,6,5,9 (6 nodes). Let's root arbitrarily, but compute for each edge:
Edge (8-9): cut: component with 9 has university 9 => 1. Other side: rest has universities 3,2,1,6,5 => 5. min=1.
Edge (3-2): cut: component with 3 has? nodes 3? plus? also 3 connected to 4 and maybe others? Actually edge (3,2) only; component with 3 includes 3,4,5? because 3-4,4-5 edges. Also maybe others? Let's build tree: nodes: 1-9. Edges: (2,1), (2,3), (2,7), (2,8), (3,4), (4,5), (7,6), (8,9). So it's like star centered at 2? Actually 2 connected to 1,3,7,8. 3 connected to 2,4; 4 connected to 3,5; 7 connected to 2,6; 8 connected to 2,9. So tree structure: 2 is root. So we can compute counts in each subtree if we root at 2.
But better: compute for each edge by seeing number of universities on each side.
Edge (2-1): component with 1 has university 1 =>1; other side (rest) has 5? total=6 => min=1.
Edge (2-3): component with 3 includes nodes 3,4,5. Universities in that component: 3,5? Actually universities: 3 and 5 (since 5 is university) and maybe? 4 is not. So count=2. Other side (rest) has universities: 2,1,6,9 =4? Actually 2 is university, yes; 1; 6; 9. That's 4. min=2.
Edge (2-7): component with 7 includes 7 and 6. Universities: 6 only => count=1. Other side has 5? total 6 => min=1.
Edge (2-8): component with 8 includes 8 and 9. Universities: 9 only => count=1. Other side has 5 => min=1.
Edge (3-4): component with 4 includes 4 and 5. Universities: 5 only => count=1. Other side (rest) has universities: all others: 3,2,1,6,9 =>5. min=1.
Edge (4-5): component with 5 has university 5 =>1; other side has 5 => min=1.
Edge (7-6): component with 6 has university 6 =>1; other side has 5 => min=1.
Edge (8-9): component with 9 has university 9 =>1; other side has 5 => min=1.
Now sum all mins: Let's sum: (8-9):1, (3-2):2, (2-7):1, (2-8):1, (2-1):1, (3-4):1, (4-5):1, (7-6):1, (8-9) already counted? Actually (8-9) we have. So total = 1+2+1+1+1+1+1+1 = 9? plus maybe (2-?) Actually we have edges: (2,1), (2,3), (2,7), (2,8), (3,4), (4,5), (7,6), (8,9). That's 8 edges. Sum = (2,1):1, (2,3):2, (2,7):1, (2,8):1, (3,4):1, (4,5):1, (7,6):1, (8,9):1 = 1+2+1+1+1+1+1+1 = 9. Yes matches output 9.
So indeed the answer seems to be sum over edges of min(S, 2k - S) where S is number of universities in one side (like subtree if we root tree arbitrarily). But we must verify if this is always achievable. This is a known problem: "Maximum sum of distances over pairing nodes in tree" often solved by greedy: each edge contributes min(cnt, 2k - cnt) because we can pair universities across that edge as much as possible, and it's possible to realize all contributions simultaneously because we can pair arbitrarily with a global construction like: for each edge, we can pair nodes across it as much as possible by ensuring that within each component we pair excess nodes internally. This is analogous to "maximum sum of distances for matching on tree" where we can compute as sum of contributions.
I think we can prove by induction that there exists a pairing achieving sum = sum_e min(cnt_e, 2k - cnt_e). Alternatively, we can argue that the total maximum distance is also equal to sum of distances of all pairs times something? Not exactly.
Alternative viewpoint: For each edge, its contribution is the number of pairs that cross it, which is at most min(cnt, 2k-cnt). Since the contributions sum to total distance, the total maximum is at most sum_e min(cnt, 2k-cnt). But is it achievable? We need to show that we can pair such that for each edge, the number of crossing pairs equals exactly min(cnt, 2k-cnt). This is like we want to achieve the upper bound.
Consider the following: For each edge, the number of crossing pairs is determined by the pairing. But constraints across edges: For any partition of nodes into two sets via an edge, crossing count = number of pairs with one node in each set. That equals, given the pairing, the number of pairs that have one endpoint in left and one in right. For a fixed pairing, the crossing count for edge (u,v) is something like: If we consider the tree as rooted, and for each node, we can compute something.
There is known result: In a tree, maximum sum of distances for pairing up 2k marked nodes can be achieved by pairing nodes as far apart as possible; equivalently, we can think of each edge being used as many times as possible, which is min(subtree_mark, 2k - subtree_mark). And it's achievable by a simple greedy: for any node, pair as many unmatched marks from different subtrees as possible, etc. Actually, typical solution for such problems (like Codeforces problem "Tree and Queries" maybe) is to compute sum of min(subtree_size, 2k - subtree_size). Let’s recall: There is Codeforces problem "1092F? Or maybe "Kefa and Park"? Not exactly. There is problem "C. George and Job"? Not.
But I'm aware of a known problem: "E. Tree Queries" or "D. Maximum Sum of Distances"? Actually, there is CF problem "D. Maximum Sum of Distances" I think? Might be CF round #104? However, many participants solved it by computing for each edge: contribution = min(size_subtree, 2k - size_subtree). So I'm confident this is correct.
Thus algorithm:
- Input n, k, list of 2k university nodes.
- Build adjacency list.
- Compute total universities count = 2k.
- Perform DFS from root (say 1) to compute for each node, number of universities in its subtree (including itself).
- For each edge (parent-child), let s = university count in child's subtree. Then contribution = min(s, total - s). Add to answer.
- Output sum.
Because tree is undirected, when we DFS, we can treat parent-child edges. For each such edge, the removal separates the tree into the child's subtree and the rest. So min(s, total-s) is correct.
Complexity O(n).
Edge Cases: Some universities may be repeated? Input says distinct, so okay.
Let's test on sample.
We already matched.
Another test: n=2, k=1, universities 1 and 2. Tree edge: 1-2. Subtree: root 1, child 2 has s=1, total=2, min=1 => answer 1 (distance 1). That's correct.
Another: n=3, k=1, universities 1 and 3, tree path 1-2-3. root at 1: compute subtree sizes: for edge 1-2: child 2 subtree includes 2 and 3? But careful: DFS from 1: child 2 has nodes 2,3. Universities in that subtree: only 3? So s=1, total=2 => min=1. Edge 2-3: child 3 subtree s=1 (uni 3) => min=1. Sum=2. Actual max distance: Only one pair (1,3) distance 2, sum=2. Works.
Another: n=3, k=1, universities 1 and 2, tree: 1-2-3. root at 1: child 2 subtree includes 2,3; s=1 (uni 2) => min=1. Edge 2-3: child 3 s=0 => min=0 => sum=1. Actual max: Pair (1,2) distance 1, sum=1. Works.
If universities are both in same subtree? That's fine.
Now, check if the bound is always achievable: Consider a star: center node 1 connected to leaves 2..n. Suppose universities are on leaves maybe. For edge (1, leaf i), s in leaf subtree is 1 if leaf is uni, else 0. So contribution = min(1, total-1) = 1 if leaf is uni, else 0. Sum over all leaf edges = number of universities (since each uni leaf contributes 1). Actually total unis = 2k. If all unis are leaves, then sum = 2k. Is this achievable? Pairing: We need to pair up 2k leaves. Maximum total distance sum: each pair of leaves distance is 2 (leaf1-center-leaf2). So total if we pair all leaves, each pair contributes 2, so sum = k * 2 = 2k. Indeed matches. If we had one uni at center and others at leaves? Let's test: n=5, unis at 1 (center) and leaves 2,3,4. total 4? Actually 2k=4, but here 1,2,3,4 -> 4 unis. Edge contributions: For each leaf edge, s in leaf subtree = 1 if leaf is uni, so for leaf2,3,4 => s=1 => min=1 (since total=4, total-s=3, min=1). For leaf5 (non-uni) s=0 => min=0. So sum=3. But total max distance? We need to pair 4 nodes. Pairing including center: The center is node1. Distances: center-leaf =1, leaf-leaf =2. To maximize sum, we should avoid pairing center with leaf as much as possible, because that gives only 1 vs 2. Since we have odd number? Actually 4 nodes: one center, three leaves. We must pair all. Pairing: best is to pair the three leaves among themselves? But three leaves cannot all be paired without one leftover; the leftover must pair with center. So we have one leaf-leaf pair (distance 2) and one center-leaf pair (distance 1) -> total 3. Or two leaf-leaf pairs? That would require 4 leaves, but we have only 3 leaves and center, so maximum is 3. Sum matches. If we had two centers? Not possible. So seems consistent.
Thus solution appears trivial: compute subtree university counts and sum min(count, total-count) for each edge.
But wait: Is there any nuance? The problem statement: "Help the Ministry to find the maximum total distance. Of course, each university should be present in only one pair." So we need to output the maximum total distance.
We derived answer = sum over edges of min(cnt, 2k-cnt). But is that always maximum? Could there be a pairing that yields even larger total distance? The upper bound is sum_e min(cnt, total-cnt) because each edge can contribute at most min(cnt, total-cnt). Since total distance is sum of contributions over edges, the maximum possible total distance ≤ sum_e min(cnt, total-cnt). And we have shown with examples that equality is attainable. Need to argue it's always attainable.
One constructive proof: Consider any edge e. Let A be number of universities in one component after removal, B = total - A. To achieve the upper bound, we need exactly min(A,B) pairs crossing e. That means we need to pair as many universities as possible across e. This suggests a greedy pairing: For each edge, we try to pair universities from different sides. This can be done by a global matching: The condition that for each edge, the crossing count equals min(A,B) is equivalent to the property that there is no edge where we could have more crossing pairs. In other words, we want to avoid pairing two universities from the same component if there is an unmatched university in the other component. This resembles the condition that in each component, the number of universities that are matched internally should be as small as possible, i.e., only the excess (|A-B|) are matched internally. So we need to design a matching that, for every cut, the number of cross pairs is exactly min(A,B). This is reminiscent of the concept of "maximum matching" across cuts, and it's known that such a perfect matching exists for any bipartite? Actually, we are matching within the same set of 2k nodes, not necessarily bipartite. However, we can think of it as: We want to match universities to maximize sum of distances. The distance can be expressed as sum over edges of indicator. The objective is linear in the matching variables? Not linear because each pair contributes to many edges. But there's an alternative viewpoint: For each pair, its distance is the number of edges on its path, so sum of distances = sum over edges of number of pairs whose path includes that edge. So it's a sum of contributions per edge. Since edges are independent in the sense that the maximum for each edge can be achieved simultaneously, we can argue by induction on tree.
Consider leaf edge: connect leaf node to rest. If leaf has a university, then we want to pair it with a university from the rest if possible. If there are more universities in rest, we can pair it cross. If leaf has no university, no crossing possible. This seems straightforward.
A constructive method: Perform DFS from root, returning a list of unmatched universities in each subtree, and then pair across subtrees as much as possible at each node. At each node, we combine the lists of unmatched universities from its children, and we can pair universities from different child subtrees (which yields crossing of the edges from node to those children). By pairing within the node, we can ensure that at most one university remains unmatched in the subtree (the excess). This is a typical greedy algorithm used in problems like "Maximum sum of distances by pairing nodes" and it yields the sum = sum_e min(cnt, total-cnt). Let's sketch:
We root the tree arbitrarily. For each node, we compute the number of universities in its subtree. Then, while processing children, we can decide to pair universities from different child subtrees, but the crossing of the edge from node to child is counted when we pair a university in child's subtree with a university outside that child's subtree. If we pair two universities both within the same child's subtree, then that pair does not cross the edge to that child. To maximize contributions, we want to minimize such internal pairings; i.e., we want to pair as many universities as possible from the child's subtree with universities outside it. The number of universities from the child's subtree that can be paired externally is min(cnt_child, total - cnt_child). But since total - cnt_child is the number of universities outside that subtree, that is the maximum possible crossing for that edge. To achieve this, we must ensure that at most |cnt_child - (total - cnt_child)| = |2cnt_child - total| universities are paired internally within the subtree, i.e., the excess if cnt_child > total/2, or all if cnt_child <= total/2? Actually, if cnt_child <= total/2, then all cnt_child can be paired externally, leaving 0 inside. If cnt_child > total/2, then only total - cnt_child can be paired externally (since there are only that many external nodes), so cnt_child - (total - cnt_child) = 2cnt_child - total must be paired internally. So the number of internal pairs within child's subtree is floor((2cnt_child - total)/2)?? Actually, internal pairings means two nodes from same child subtree form a pair. Each internal pair uses 2 nodes from that subtree, reducing the number of nodes available to cross the edge by 2. So the number of nodes crossing the edge = cnt_child - 2 * internal_pairs_within_subtree. To maximize crossing, we want internal_pairs_within_subtree as small as possible, given that we must pair all nodes globally. The minimum possible internal pairs within a subtree is max(0, cnt_child - (total - cnt_child))? Let's derive: The maximum number of nodes from this subtree that can be paired with external nodes is at most total - cnt_child (the number of external nodes). So the number of nodes that must stay within is cnt_child - (total - cnt_child) if this is positive; else 0. Those leftover nodes must be paired among themselves, which yields floor(leftover/2) pairs internal. But note, leftover could be odd? However, total number of universities is even (2k), so globally things will work out parity wise. Indeed, if cnt_child > total - cnt_child, then leftover = 2cnt_child - total, which is even? Since cnt_child and total are both numbers; total is even (2k), so 2cnt_child - total is even. So yes, internal pairs = (2cnt_child - total)/2. That is exactly the number of pairs that do not cross the edge. Then the crossing pairs contributed by this edge = (cnt_child - leftover) = total - cnt_child, but also = min(cnt_child, total-cnt_child). Actually, crossing pairs = number of nodes from subtree paired externally = min(cnt_child, total - cnt_child). Because each such node pairs with an external node, and each external node is used at most once per edge? But careful: each external node can pair with at most one subtree node? Actually, if we pair a node from subtree A with a node from subtree B (both children of same parent), then for edge to child A, that node is crossing; for edge to child B, that node is crossing as well. That's fine; the counting per edge is independent. So for edge to child, crossing count = number of nodes in child subtree that are paired with nodes outside that subtree. To achieve max, we want this number = min(cnt_child, total-cnt_child). And this is feasible if we globally pair such that within each subtree, only the excess (if any) are paired internally. The greedy algorithm that, at each node, pairs as many nodes from different child subtrees as possible, will achieve this. The internal pairing within a subtree will be handled recursively.
Thus the maximum total distance equals sum over edges of min(cnt_subtree, total - cnt_subtree). So algorithm stands.
Implementation steps:
- Read n, k.
- Read list of 2k university indices.
- Build adjacency list of size n+1.
- Create a boolean array isUni[1..n] set false initially; for each uni, mark true.
- Do DFS from 1 (or any root). We'll use recursion? But n up to 200k, recursion depth might cause stack overflow in Python if not careful. Use iterative DFS or set recursion limit high and hope? 200k depth could be a chain, so recursion may exceed Python recursion limit even if increased? Default is 1000. We can set sys.setrecursionlimit(300000) or more. Python recursion depth may cause RecursionError if tree is deep 200k, but we can set recursionlimit to 500000. However, Python recursion overhead may be okay, but there is risk of hitting recursion depth limit or stack overflow due to C stack? Usually setting recursionlimit high allows deep recursion, but if the tree depth is 200k, each recursion call uses some memory, could cause memory error? Typically, Python's recursion stack uses a lot of memory and may cause segmentation fault if too deep. Safer to implement iterative DFS using stack.
We'll implement iterative post-order traversal. For each node, compute subtree uni count. We can do:
- Use stack for DFS order: push (node, parent, state) where state 0 means before children, state 1 means after children.
- Alternatively, we can do a simple stack to get order, then process in reverse.
Simpler: Perform a stack for traversal to get parent and order. We'll do:
stack = [1] parent = [0]*(n+1) order = [] while stack: u = stack.pop() order.append(u) for v in adj[u]: if v != parent[u]: parent[v] = u stack.append(v)
But careful: This will produce a depth-first order but children might be processed before parents? Actually if we push children onto stack, the order list will have nodes in the order of visitation (preorder). When we later reverse order, we get nodes from leaves up to root. So we can compute subtree counts by iterating reversed order.
We'll maintain cnt[u] = isUni[u] (1 or 0). For each node u in reversed order (excluding root? but we want all), for each child v where parent[v]==u, cnt[u] += cnt[v]. We'll also compute contribution for edge (u,v) when processing child v: contribution += min(cnt[v], total - cnt[v]).
But careful: In reversed order, when we process node u, its children (which have been processed earlier in reversed order) have already added to cnt[u]. So we can compute contributions when we have cnt[child] computed. So we can loop over all nodes except root? Actually we can compute contribution for each edge when we process the child node. So after we have cnt array, we can iterate over all nodes (except root) and for each node v (v != root), let u = parent[v]; then contribution += min(cnt[v], total - cnt[v]).
That works.
Total = 2k.
Edge Cases: ensure total - cnt[v] is positive? It could be zero if all universities are in subtree, but min handles.
Thus answer is sum.
Now test on examples.
Implementation in Python:
def solve(): import sys sys.setrecursionlimit(400000) data = sys.stdin.read().split() it = iter(data) n = int(next(it)); k = int(next(it)) total_uni = 2k is_uni = [0](n+1) uni_list = [int(next(it)) for _ in range(total_uni)] for u in uni_list: is_uni[u] = 1 adj = [[] for _ in range(n+1)] for _ in range(n-1): x = int(next(it)); y = int(next(it)) adj[x].append(y) adj[y].append(x) # BFS/DFS to set parent and order parent = [0](n+1) order = [] stack = [1] parent[1] = -1 # mark root while stack: u = stack.pop() order.append(u) for v in adj[u]: if v != parent[u]: parent[v] = u stack.append(v) cnt = [0](n+1) # compute subtree counts for u in reversed(order): cnt_u = is_uni[u] for v in adj[u]: if parent[v] == u: # v is child of u cnt_u += cnt[v] cnt[u] = cnt_u total = total_uni ans = 0 for v in range(2, n+1): # nodes except root? but root might not be 1 if we start at 1. Actually we set root as 1. So for each node v where parent[v] != 0 (or parent[v] != -1) if parent[v] != -1: # but we set parent[1] = -1; for others parent is set. s = cnt[v] ans += min(s, total - s) print(ans)
But need to be careful: In the parent assignment, we set parent[1] = -1, but we didn't set parent for other nodes that might have multiple? It's fine.
Alternatively, we can loop over all nodes and for each child, we add contribution, but ensure not to count both directions. Since we have parent array, we can just iterate over v from 1 to n, if parent[v] != 0 and parent[v] != -1? Actually we used -1 for root, but for other nodes parent is set to the actual parent. So we can loop v = 2..n as above.
But what if root is not 1? We started DFS from 1 arbitrarily. Since tree is connected and undirected, any root works. So we can root at 1. That's fine.
But we must ensure that for every edge, we count exactly once. Our method counts each edge when considering the child side. Since we have a rooted tree, each edge is represented as parent-child. So it's fine.
Now test with provided examples.
Example 1:
n=7, k=2, unis: [1,5,6,2]; edges as given.
We'll simulate quickly: root=1. Parent: from DFS stack order might vary, but tree is small. We'll compute counts. Let's compute manually: root=1. children: from adj[1] = [3] (since only edge 1-3). So parent[3] =1. Then from node 3, adj[3] = [1,2,7,4]. Since parent[3]=1, children are 2,7,4. So parent[2]=3, parent[7]=3, parent[4]=3. From node 2, adj[2] = [3] only? also maybe? Actually edge list: 3-2, so adj[2] = [3]. So 2 has no children except parent. Node 7 similarly. Node 4: adj[4] = [5,3,6] so children: 5 and 6 (since parent is 3). So parent[5]=4, parent[6]=4. Node5 adj[5]=[4] no child; node6 adj[6]=[4] no child. So order might be something: e.g., stack=[1] pop 1, push children? Actually our code: stack = [1]; while stack: u = stack.pop(); order.append(u); for v in adj[u]: if v != parent[u]: parent[v]=u; stack.append(v). This is using stack LIFO, so it's depth-first but order depends on adjacency list order. Let's not worry. Reversed order will process leaves first.
Compute cnt: is_uni: 1,2,5,6 are 1, others 0.
At leaves: node2: cnt=1 (since is_uni[2]=1). node7:0. node5:1. node6:1. node4: cnt = is_uni[4]=0 + cnt[5]=1 + cnt[6]=1 =2. node3: cnt = is_uni[3]=0 + cnt[2]=1 + cnt[7]=0 + cnt[4]=2 =3. node1: cnt = is_uni[1]=1 + cnt[3]=3 =4. total=4.
Now contributions: For each child: v=2: s=1, total-s=3 => min=1. v=7: s=0 =>0. v=4: s=2 => min=2. v=5: s=1 =>1? but wait, we treat v as any node with parent? Our loop for v from 2 to n includes all nodes except 1. So we include v=5: parent[5]=4, so we add min(cnt[5]=1, total-1=3)=1. v=6: s=1 =>1. v=3: parent[3]=1, so we add min(cnt[3]=3, total-3=1)=1. v=2,4,5,6,7,3? Actually we have nodes: 2,3,4,5,6,7. That's 6 edges? Tree has 6 edges. Let's list contributions: v=2: edge 3-2 => 1 v=3: edge 1-3 => min(3,1)=1 v=4: edge 3-4 => min(2,2)=2 v=5: edge 4-5 => min(1,3)=1 v=6: edge 4-6 => min(1,3)=1 v=7: edge 3-7 => min(0,4)=0 Sum = 1+1+2+1+1+0 = 6. Good.
Second example would also match.
Thus algorithm works.
Now time complexity: O(n). Memory: O(n).
We must be careful with Python I/O due to large input. Use sys.stdin.read.
Potential pitfalls: if root is 1 but there may be no university at 1, that's fine.
Edge Cases: If k=0? But constraints say k>=1, and n>=2, so not needed.
But total uni = 2k could be zero? No.
Also note: tree may be large, recursion depth may be okay if we use iterative.
We'll implement iterative to be safe.
Now, is there any scenario where the answer is not simply sum min? Let's test a more complex tree manually to ensure.
Consider a tree that is a line of 5 nodes: 1-2-3-4-5. Universities at nodes 1,2,4,5 (2k=4). Total nodes:5. root at 1? We'll compute contributions:
If we root at 1: Edges: (1-2): subtree of 2 includes nodes 2,3,4,5. unis: 2,4,5 => cnt=3, total=4 => min=3? Actually min(3,1)=1. Wait total-cnt=1, min=1. (2-3): subtree of 3 includes 3,4,5 => unis:4,5 => cnt=2 => min(2,2)=2. (3-4): subtree of 4 includes 4,5 => unis:4,5 => cnt=2 => min(2,2)=2. (4-5): subtree of 5 includes 5 => uni 5 => cnt=1 => min(1,3)=1. Sum = 1+2+2+1 = 6.
Now, can we achieve total distance 6? Let's list possible pairings: nodes 1,2,4,5. Distances: d(1,2)=1; d(1,4)=3; d(1,5)=4; d(2,4)=2; d(2,5)=3; d(4,5)=1. We need two pairs covering all 4 nodes. Pair possibilities:
- (1,2)+(4,5): total = 1+1=2.
- (1,4)+(2,5): total = 3+3=6.
- (1,5)+(2,4): total = 4+2=6. Thus max is 6, matches.
Now consider a balanced binary tree maybe. So seems correct.
Now, let's reason more formally: The total distance = sum_e I_e, where I_e is number of pairs crossing edge e. For a fixed pairing, I_e equals the number of pairs with one node on each side. Since each pair contributes at most 1 to I_e (if its two endpoints lie on different sides). The maximum possible I_e is min(cnt, total-cnt) as argued. And this maximum can be achieved for all e simultaneously by a pairing that, for each e, ensures that exactly min(cnt, total-cnt) pairs cross it. The existence of such a pairing can be proved via a greedy algorithm that processes the tree bottom-up: At each node, we combine the multisets of "unmatched" universities from its children. The idea: For each child subtree, we can treat the number of universities that are "available" to be matched outside as something. In each child subtree, after internal pairing, there will be either 0 or 1 leftover (since total even? Actually, we can always arrange that at most one unmatched university per subtree? Let's think: In a subtree with cnt universities, if we pair as many as possible across the edge to its parent, we would like to leave at most |2*cnt - total|? Hmm.
Standard solution: In Codeforces problem "1092F? Actually there is problem "E. Tree Queries"? Not. Another known problem: "B. Karen and Coffee"? No.
But I'm convinced.
Thus final solution: compute subtree counts and sum min(cnt_sub, total - cnt_sub).
Potential pitfalls: The total variable is 2k, which is even. The answer fits in 64-bit (max edges n-1=199,999, each min up to k? Actually min(cnt, 2k-cnt) ≤ k, since maximum min is when cnt = k, min = k. So total ≤ (n-1) * k. n up to 200k, k up to 100k, product up to 2e10, fits in 64-bit (Python int is arbitrary, fine).
Now, implement.
One more check: The input says "2k distinct integers u1, u2, ..., u2k" but not necessarily that 2k ≤ n? Since k ≤ n/2, 2k ≤ n, so okay.
Implementation details:
- Use adjacency list as list of lists.
- Use sys.stdin.buffer.read() for faster reading.
We'll parse all ints.
Edge Cases: There might be multiple test cases? Problem statement suggests single test case. So just read and output.
Let's write solve() function.
Potential improvement: We can compute contributions while doing DFS without storing parent array? But that's fine.
Alternatively, we can do recursive DFS with sys.setrecursionlimit(1000000). Many Python solutions do that for 200k. But to be safe, we implement iterative.
Let's write code:
import sys
def solve(): data = sys.stdin.buffer.read().split() it = iter(data) n = int(next(it)) k = int(next(it)) total_uni = 2 * k is_uni = [0] * (n + 1) for _ in range(total_uni): u = int(next(it)) is_uni[u] = 1 adj = [[] for _ in range(n + 1)] for _ in range(n - 1): x = int(next(it)); y = int(next(it)) adj[x].append(y) adj[y].append(x)
parent = [0] * (n + 1) order = [] stack = [1] parent[1] = -1 while stack: u = stack.pop() order.append(u) for v in adj[u]: if v != parent[u]: parent[v] = u stack.append(v) cnt = [0] * (n + 1) for u in reversed(order): c = is_uni[u] for v in adj[u]: if parent[v] == u: # v is child c += cnt[v] cnt[u] = c total = total_uni ans = 0 for v in range(2, n + 1): # v != 1, parent is set s = cnt[v] ans += min(s, total - s) print(ans)if name == "main": solve()
But careful: In the for v in range(2, n+1), we assume root is 1 and all other nodes have parent != 0. But what if the tree is rooted such that 1 is isolated? No, it's connected, so fine.
But there is nuance: The parent assignment used stack may not guarantee that parent[1] = -1 and for all others parent is set to some non-zero. But if n=1? Not possible. So fine.
Potential bug: In the loop for reversed order, we check "if parent[v] == u" to identify child. That works because parent[child] = u. However, we must ensure that in the reversed order we have parent assigned correctly. Yes.
Alternatively, we could compute contributions while processing children after cnt computed: for v in range(2,n+1): s = cnt[v]; ans += min(s, total-s). That's simpler.
But we must ensure that for each edge we count only once, and we do by counting child's side. Since we rooted at 1, all edges are counted exactly once (except maybe if we count node 1 as child? no, we skip root). So good.
Now, test with second sample using mental or quick simulation? Already matched.
Edge case: What if root 1 has no universities? That's fine.
What if total uni = 0? Not possible.
Thus solution done.
But wait, is it always correct to sum min(cnt_subtree, total - cnt_subtree)? Let's double-check with a more complex tree where internal edge contributions might conflict. For example, a tree shaped like: root with two big subtrees each containing k universities. Then for edge from root to each subtree, cnt = k, total - cnt = k, min = k. So sum contributions = 2k? But number of edges maybe more. Actually, if each subtree edge gets k, total maybe? But total distance maximum? Let's test: root 0, left subtree has k universities, right subtree has k universities. For edges connecting root to left, min=k. For edges inside left subtree, contributions will sum to something else. Let's consider simple case: root 1 connected to left node A and right node B. A and B are each centers of stars with many leaves. Actually, suppose root is node R. Left subtree is a chain of nodes leading to a leaf cluster with k universities; the contributions from edges inside left subtree may be limited. But overall, the sum of mins should be the maximum.
I recall a known Codeforces problem: "E. Tree" or "D. Maximum Sum of Distances". Actually, problem is from Codeforces Round #104? The exact problem: "D. Maximum Sum of Distances" maybe not. But there is problem "C. Fox And Names"? Not.
But there's a known solution: answer = sum over edges (min(uni_subtree, 2k - uni_subtree)). So I'm confident.
Thus we will produce final answer.
Now, we might consider memory: adjacency list of size up to 200k+1, each storing up to degree. That's fine.
We'll implement with Python's sys.stdin.buffer.
But we need to be careful: When using sys.stdin.buffer.read().split(), it loads all input into memory; for 200k lines, that's okay.
Now, I think the solution is ready.
But before finalizing, let's consider whether any alternative interpretation could be: The ministry wants to connect each university with another one by using a cable, and they want to maximize total length. They will pair them. That's exactly what we solved.
One might think that they need to physically lay cables along paths, and they might share edges? That doesn't matter, because we sum distances, regardless of overlap.
Thus answer.
Now, implementation details:
-
We used parent array and reversed order. This is standard.
-
The loop for v in range(2,n+1) includes all nodes except 1, but what about node that is not reachable from 1? Not possible.
-
However, if root is 1, and some node's parent may be 0 if not visited? But our DFS visited all because tree is connected.
Edge Cases: n=200k, maximum recursion? We used iterative.
Potential micro-optimizations: Use ints and local variables.
We can also compute contributions during DFS without storing order: Use recursion to compute cnt and add to ans when returning. But iterative is fine.
Let's write final answer.
But we might need to consider that Python might be slow for loops over adjacency for each node in reversed order because each node's children are iterated twice: once in DFS to set parent, and again when computing cnt. Actually we iterate adjacency twice: in DFS and in reversed order. That's O(n) total anyway. 200k is fine.
We could combine both steps: do a stack that also computes counts in postorder using two stacks. But fine.
Alternatively, we could compute cnt using a single DFS that returns count and updates ans. That would be simpler in recursion but risk recursion depth. But we can implement iterative postorder using stack with state.
Maybe simpler: Use recursion with setrecursionlimit(10**6) and hope. Many Python solutions on CF use recursion for trees up to 2e5, but it's known that Python recursion can cause RecursionError or TLE due to recursion overhead? Actually, recursion overhead in Python is high but might still pass if not too deep? But depth can be 200k, which might cause recursion limit issues even if increased, because Python's recursion uses C stack and can cause segmentation fault if too deep (limit about 1000 default, but increasing recursionlimit only allows more Python frames, but the underlying C stack may still overflow if depth > ~1000? Actually, CPython uses C stack for function calls; setting recursionlimit high just allows more Python frames, but the C stack size is limited and might overflow for deep recursion (e.g., 10k+). I've seen that for depth around 10^5, Python often crashes. So better to avoid recursion.
Thus iterative is safer.
We'll keep iterative.
Now, finalize answer.
Let's also consider if there is any nuance about the root: The min(cnt, total-cnt) formula works for any edge, but we need to make sure that cnt for child subtree is correct. In our calculation, cnt[v] is the number of universities in subtree of v when tree is rooted at 1. For edge between v and its parent, the side containing v has cnt[v] universities; the other side has total - cnt[v]. So min is correct. So we sum over all v != root.
Now, answer.
We'll provide explanation in final message.
But the user asked: "Help the Ministry to find the maximum total distance." So we need to output maximum sum.
Thus final solution.
Now, let's double-check with a random test to ensure no off-by-one.
Consider tree with 2 nodes: n=2, k=1, unis: [1,2], edge: 1-2. Root at 1: cnt[2]=1, total=2 => min(1,1)=1. ans=1. correct.
If unis: [1,2] but n=2, same.
Consider tree with 3 nodes: 1-2-3, unis: [1,2] (k=1). root at 1. cnt[2]? Let's compute: nodes: 1 is root, child 2, child of 2 is 3. is_uni[1]=1,2=1,3=0. So cnt[3]=0; cnt[2] = is_uni[2] + cnt[3] = 1; cnt[1] = 1 + cnt[2] = 2. total=2. contributions: v=2: min(cnt[2]=1, 1) =1; v=3: min(cnt[3]=0,2) =0; ans=1. Actual max: only pair (1,2) distance 1, sum=1. correct.
Consider tree with 4 nodes: chain 1-2-3-4, unis: [1,4] (k=1). root at 1. is_uni: 1,4. Compute cnt: node4:1; node3: is_uni[3]=0 + cnt[4]=1 =>1; node2: is_uni[2]=0 + cnt[3]=1 =>1; node1:1 + cnt[2]=1 =>2. total=2. contributions: v=2: min(1,1)=1; v=3: min(1,1)=1; v=4: min(1,1)=1. sum=3. Actual max: pair (1,4) distance 3, sum=3. correct.
Consider tree with 4 nodes: star: 1 center, leaves 2,3,4. unis: [2,3,4]? but 2k must be even, so we need 2 unis. Let's take unis: [2,3] (k=1). root at 1. cnt[2]=1, cnt[3]=1, cnt[4]=0, cnt[1] = sum =2. contributions: v=2: min(1,1)=1; v=3: min(1,1)=1; v=4: min(0,2)=0 => sum=2. Max total distance: pair (2,3) distance 2 (2-1-3). So sum=2. correct.
Now, if unis: [2,4] similarly.
Consider unis: [2,3,4,?] need 4. So k=2, unis: [2,3,4,?]. But only 3 leaves, need 4th uni at center? Let's test earlier example.
Works.
Now, consider a tree where universities are all in one subtree of root. For edge from root to that subtree, cnt = 2k, total - cnt = 0 => min = 0. That seems right: you can't pair across that edge because there are no universities outside. So contributions zero. For edges inside that subtree, they may have contributions.
Let's test: chain 1-2-3-4, unis: [2,3] (k=1). root at 1. cnt[2] includes 2,3? Actually compute: is_uni:2,3. cnt[4]=0; cnt[3] = 1; cnt[2] = is_uni[2]=1 + cnt[3]=1 =>2; cnt[1]=0+ cnt[2]=2 total=2. contributions: v=2: min(2,0)=0; v=3: min(1,1)=1; v=4: min(0,2)=0 => sum=1. Actual max: only one pair (2,3) distance 1, sum=1. correct.
Now, if unis: [1,2,3,4] (k=2) chain 1-2-3-4. root at 1. cnt[4]=1; cnt[3]=2; cnt[2]=3; cnt[1]=4. total=4. contributions: v=2: min(3,1)=1; v=3: min(2,2)=2; v=4: min(1,3)=1 => sum=4. Maximum pairing: pair (1,4) distance 3, (2,3) distance 1 => total 4; or (1,3)=2, (2,4)=2 => total 4. So max 4. correct.
Thus formula seems robust.
Now, confirm with a more complex tree: balanced binary tree of 7 nodes (root 1, children 2,3, leaves 4,5,6,7). Let's assign unis: leaves 4,5,6,7 (k=2). root at 1. Compute subtree counts: root's left child 2 has children 4,5; right child 3 has children 6,7. cnt[4]=1, cnt[5]=1, cnt[2]=2, cnt[6]=1, cnt[7]=1, cnt[3]=2, cnt[1]=4. contributions: Edge 1-2: min(2,2)=2 Edge 1-3: min(2,2)=2 Edge 2-4: min(1,3)=1 Edge 2-5: min(1,3)=1 Edge 3-6: min(1,3)=1 Edge 3-7: min(1,3)=1 Sum = 2+2+1+1+1+1 = 8. Maximum total distance: Pair across as far as possible. Pair (4,7) distance: 4-2-1-3-7 => 4 edges? Actually path: 4-2-1-3-7: 4 edges? Let's count: 4 to 2 (1), 2 to 1 (1), 1 to 3 (1), 3 to 7 (1) => total 4. Similarly (5,6) distance 4. Sum=8. Also (4,6) would be 3? Actually 4-2-1-3-6: also 4 edges? Wait 4-2(1),2-1(1),1-3(1),3-6(1) =4. So all cross pairs are 4. So sum=8, matches.
If we paired (4,5) within left: distance 2, and (6,7) within right: distance 2, total=4, not max.
Thus works.
Now, final answer.
But let's consider a scenario where there is an edge with cnt = total/2 exactly. Then min = total/2 = k. That's okay.
Thus algorithm is correct.
Now, is there any subtlety about using Python's recursion? We already decided iterative.
Now, what about input size: 200k lines, using read().split() is okay.
We'll produce final solution.
But maybe we can optimize memory: not storing is_uni as int list, we could store cnt directly as we go? But we need initial marks.
Ok.
Now, we can also compute contributions during the reversed order loop instead of separate loop: after computing cnt[u], if parent[u] != -1, we can add min(cnt[u], total - cnt[u]) to ans. That would be more efficient, as we avoid second loop over nodes. Let's adjust:
After cnt[u] computed in reversed order, we can check if parent[u] != -1 (i.e., u is not root). Then ans += min(cnt[u], total - cnt[u]).
Because at that point, cnt[u] is known. This is better.
Let's implement that:
for u in reversed(order): c = is_uni[u] for v in adj[u]: if parent[v] == u: c += cnt[v] cnt[u] = c if parent[u] != -1: ans += min(c, total - c)
Yes.
Now, finalize.
Edge: parent[1] = -1, so for u=1 we skip.
Now, code.
We'll also note that we might need to use long (Python int).
Now, we'll produce final answer.
But also consider if the tree is rooted at 1, but 1 may have parent=0? We set to -1, but then check parent[u] != -1; for other nodes, parent is set to a positive int. So fine.
Now, testing on samples:
First sample: order reversed? But algorithm will compute same.
Let's quickly simulate:
First sample with our algorithm:
Build adjacency, DFS stack order could be different but result same.
We trust.
Now, final answer.
Now, provide explanation in final response.
The user asked "Help the Ministry to find the maximum total distance." So output.
Thus final message: Provide code and explanation.
We'll include reasoning: each edge contributes at most min(x, 2k-x) where x is number of universities in one side; and this bound is achievable by pairing universities across edges as much as possible. Compute via subtree counts.
Will output final answer.
Now, double-check for any pitfalls: The input includes 2k distinct integers; but we assume there are exactly 2k numbers. Could there be trailing spaces? No.
Also, ensure we convert bytes to int correctly.
Now, final code:
import sys
def solve(): data = sys.stdin.buffer.read().split() if not data: return it = iter(data) n = int(next(it)) k = int(next(it)) total_uni = 2k is_uni = [0](n+1) for _ in range(total_uni): u = int(next(it)) is_uni[u] = 1 adj = [[] for _ in range(n+1)] for _ in range(n-1): x = int(next(it)); y = int(next(it)) adj[x].append(y) adj[y].append(x) parent = [0](n+1) order = [] stack = [1] parent[1] = -1 while stack: u = stack.pop() order.append(u) for v in adj[u]: if v != parent[u]: parent[v] = u stack.append(v) cnt = [0](n+1) ans = 0 total = total_uni for u in reversed(order): c = is_uni[u] for v in adj[u]: if parent[v] == u: c += cnt[v] cnt[u] = c if parent[u] != -1: ans += min(c, total - c) print(ans)
if name == "main": solve()
Now, check memory: adjacency list with up to 400k entries (since 2*(n-1) edges). Fine.
Now, final answer.
But we might also consider that we can compute using BFS to get parent and order using deque, but stack is fine.
Now, done.
Potential oversight: When we set parent[1] = -1, and then later in the for loop we check if parent[u] != -1, that's fine. But we also need to ensure that for other nodes, parent[u] is never -1. It's set to positive integer. So okay.
Now, let's test with a case where root is not 1 but tree is still connected? Actually we rooted at 1, so all nodes reachable; since tree is connected, BFS/DFS from 1 reaches all nodes. So fine.
Now, finalize.
Now, we produce final response with explanation and code. ```python
import sys
def solve() -> None: data = sys.stdin.buffer.read().split() if not data: return it = iter(data) n = int(next(it)) k = int(next(it)) total_uni = 2 * k
# mark university towns is_uni = [0] * (n + 1) for _ in range(total_uni): u = int(next(it)) is_uni[u] = 1 # tree adjacency list adj = [[] for _ in range(n + 1)] for _ in range(n - 1): x = int(next(it)) y = int(next(it)) adj[x].append(y) adj[y].append(x) # iterative DFS to obtain parent array and order parent = [0] * (n + 1) order = [] stack = [1] parent[1] = -1 # root marker while stack: u = stack.pop() order.append(u) for v in adj[u]: if v != parent[u]: parent[v] = u stack.append(v) cnt = [0] * (n + 1) # number of universities in subtree ans = 0 total = total_uni # process nodes in reverse (post-order) to compute subtree sizes for u in reversed(order): c = is_uni[u] for v in adj[u]: if parent[v] == u: # v is a child of u c += cnt[v] cnt[u] = c if parent[u] != -1: # not the root -> edge to its parent ans += min(c, total - c) print(ans)if name == "main": solve()