The Number Games
Contest: Codeforces Round 480 (Div. 2)
Difficulty rating: 2200
Tags: data structures, greedy, trees

The nation of Panel holds an annual show called The Number Games, where each district in the nation will be represented by one contestant.

The nation has $$$n$$$ districts numbered from $$$1$$$ to $$$n$$$, each district has exactly one path connecting it to every other district. The number of fans of a contestant from district $$$i$$$ is equal to $$$2^i$$$.

This year, the president decided to reduce the costs. He wants to remove $$$k$$$ contestants from the games. However, the districts of the removed contestants will be furious and will not allow anyone to cross through their districts.

The president wants to ensure that all remaining contestants are from districts that can be reached from one another. He also wishes to maximize the total number of fans of the participating contestants.

Which contestants should the president remove?

Input format:
The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k < n \leq 10^6$$$) — the number of districts in Panel, and the number of contestants the president wishes to remove, respectively.

The next $$$n-1$$$ lines each contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq n$$$, $$$a \ne b$$$), that describe a road that connects two different districts $$$a$$$ and $$$b$$$ in the nation. It is guaranteed that there is exactly one path between every two districts.

Output format:
Print $$$k$$$ space-separated integers: the numbers of the districts of which the contestants should be removed, in increasing order of district number.

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

Note:
In the first sample, the maximum possible total number of fans is $$$2^2 + 2^5 + 2^6 = 100$$$. We can achieve it by removing the contestants of the districts 1, 3, and 4.

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

Example output:
1 3 4

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

Example output:
1 3 4 5

Editorial:
As the final set of remaining districts need to be reachable from each other, this means that the resulting tree is a sub-graph of the original one.
Now, looking at the number of fans in each district, district $$$i$$$ has $$$2^{i}$$$ fans. This means that if we had a choice of including a district $$$i$$$ in our solution and discarding all the districts with indices less than $$$i$$$ then it'd be better than discarding district $$$i$$$ and including all the others, as $$$2^{i} = 2^{i-1} + 2^{i-2} + ... + 2^{0} + 1$$$.
This leads us to the following greedy solution:
Let's try to find which districts to keep instead of which to discard, let's first root the tree at district $$$n$$$, as we can always keep it, and go through the remaining districts by the order of decreasing index. Now at each step, if we can include district $$$i$$$ into our solution by taking it and all of the nodes on the path connecting it to our current sub-graph, then we should surely do so, otherwise we can just ignore it and move on to the next district.
This can be implemented by building a parent sparse-table and using Binary Lifting at each district $$$i$$$ to find the first of its ancestors that has been already included in our sub-graph. The distance to this ancestor represents the number of districts that need to be included in the games to have district $$$i$$$ included. So if we can still include that many districts in our sub-graph then we will traverse through the path and mark them as included.
Solution Complexity: $$$O(nlogn)$$$