Solution to this -> http://codeforces.com/contest/980/problem/E

the_number_games.py

from collections import defaultdict as dd


def fill(distances, was, backlinks, top, curr, dist):
    distances[curr] = dist
    was[curr] = True
    while dist > 0:
        distances[curr] = dist
        was[curr] = True
        curr = backlinks[curr][0]
        dist -= 1

n, k = map(int, raw_input().strip().split())
tree = dd(set)
for _ in xrange(n - 1):
    fr, to = map(lambda x: int(x) - 1, raw_input().strip().split())
    tree[fr].add(to)
    tree[to].add(fr)

root = n - 1
distances = [0] * n
backlinks = [[] for _ in xrange(n)]
stack = [(root, None)]
while stack:
    curr, par = stack.pop()
    if par is not None:
        distances[curr] = distances[par] + 1
        backlinks[curr].append(par)
        i = 0
        nxt = par
        while i < len(backlinks[nxt]):
            backlinks[curr].append(backlinks[nxt][i])
            i += 1
            nxt = backlinks[curr][-1]

    for nxt in tree[curr]:
        if nxt != par:
            stack.append((nxt, curr))

need = n - k
have = 1
curr = n - 2
was = [False] * n
was[n - 1] = True

while have < need:
    if was[curr]:
        curr -= 1
        continue

    base = 0
    nxt = curr
    while not backlinks[nxt] or not was[backlinks[nxt][0]]:
        low, high = 0, len(backlinks[nxt]) - 1
        while high - low > 1:
            mid = (low + high) / 2
            if was[backlinks[nxt][mid]]:
                high = mid
            else:
                low = mid
        base += 2 ** low
        nxt = backlinks[nxt][low]

    if backlinks[nxt]:
        base += 1

    if base <= need - have:
        have += base
        top = backlinks[nxt][0] if backlinks[nxt] else root
        fill(distances, was, backlinks, top, curr, base)

    curr -= 1

print " ".join(map(str, sorted([i + 1 for i, x in enumerate(was) if not x])))