Решение D на 100 баллов

Подвесим дерево за произвольную вершину. Посчитаем две динамики на поддеревьях: f[v] - на какой глубине находится ближайшая ловушка, и g[v] - на какой глубине находится ближайший непокрытый таракан. Как делать переходы? Для текущей вершины после обработки детей посчитаем минимум по всем f[child(v)] и максимум по всем g[child(v)]. Пусть первое число - a, второе - b. Тогда возможны три ситуации.

1) a + b <= k

Тогда самый удаленный таракан покрывается самой высокой ловушкой из другого поддерева. В этом поддереве не остается непокрытых тараканов, а самая глубокая ловушка находится на глубине a+1.

f[v] = a+1, g[v] = 0

2) a + b > k, b < k

У нас есть тараканы, которых мы не можем покрыть, но они не настолько глубоко, чтобы ставить тут ловушку (если мы постави ее выше, хуже не будет).

f[v] = a+1, g[v] = b+1

3) a + b > k, b == k

Самый глубокий непокрытый таракан в поддереве не может быть покрыт иначе, кроме как из этой вершины. Ставим тут ловушку, тем самым покрывая всех непокрытых тараканов в поддереве (т к их глубина <= k).

f[a] = 0, g[a] = 0

Ну и если мы находимся в корне и у нас есть непокрытые тараканы, мы обязаны поставить там ловушку.