For the first subtask, it's optimal to connect the rightmost to the leftmost, second rightmost to the second leftmost, etc. A prefix sum can be used to speed this up.

Time Complexity: ~\mathcal{O}(N)~

For the second subtask, precompute the distance between each pair of students using BFS or DFS. Then, brute-force all possible configurations of pairs.

Time Complexity: ~\mathcal{O}(KN+K!)~

For the third subtask, root the tree arbitrarily. We think of the distances between pairs as each student moving up to their LCA. Now let ~dp[i][j]~ be the total cost within the subtree of node ~i~ such that ~j~ students are still moving up. Now, we must be able to merge a node's children's ~dp~ values. Given a set of the children's ~j~'s, note if we can find the minimum ~j~ for the node, we can obtain any larger ~j~ with the same parity and within the total sum of the ~j~'s and the node's number of students. By considering this problem, we only need to consider the maximum ~j~, and the sum of the ~j~'s. So it can be done in polynomial time. The final answer is ~dp[1][0]~.

Time Complexity: ~\mathcal{O}(NK^3)~

For the final subtask, we realize that the solution to the third subtask is absolutely awful. Root the tree at the centroid of the students (not the centroid of the entire tree!). Again, consider this problem. If we merge the children of the centroid with their maximum possible ~j~'s, then we can actually obtain ~0~, which means that all the students have been paired up. Also, since the children of the centroid have maximum possible ~j~'s, this must be the maximum possible total. So the optimal case is when all the students head to their centroid. This can be implemented in linear time.

Time Complexity: ~\mathcal{O}(N+K)~