Choose k Cities to Minimize Maximum Distance on a Tree

You are given a tree with n cities connected by n-1 roads. Your task is to select exactly k cities such that the maximum distance between any two selected cities is minimized. It is known that the tree is connected and there is exactly one unique path between any two cities.

This problem can be approached by first finding the diameter of the tree (i.e. the longest simple path) and then selecting a central contiguous segment of cities from that path. If k is greater than or equal to the length of the diameter, simply output the cities on the diameter up to k cities; otherwise, choose a segment around the middle of the diameter. The answer can be output in any order, however, for consistency we require the selected cities to be printed in ascending order.

The formulas used in selection are as follows: Let L be the length of the longest path and m be the middle index (using 0-based indexing) of the longest path. For odd k, choose the segment from index m - ((k+1)/2 - 1) to m + (k+1)/2 - 1. For even k, choose the segment from index m - (k+1)/2 to m + (k+1)/2 - 1.

inputFormat

The input is given from standard input and has the following format:

n
u1 v1
u2 v2
...
u(n-1) v(n-1)
k

Where:

• n (1 ≤ n ≤ 10^5) is the number of cities.
• Each of the next n-1 lines contains two integers u and v representing a road connecting cities u and v.
• k (1 ≤ k ≤ n) is the number of cities to be selected.

outputFormat

Output k city numbers in ascending order separated by a single space, representing the selected cities which minimize the maximum distance among them.

6
1 2
1 3
2 4
2 5
3 6
4

1 2 3 6