Коровники (задача с российских летних сборов 2007 года)

Дано дерево из n <= 50000 вершин. Нужно зафиксировать k <= n вершин так, чтобы минимизировать максимальное расстояние от вершины дерева до ближайшей фиксированной. Нужно восстановить ответ.

Я придумал что-то похожее на решение для этой задачи, но, увы, у меня не получается это довести: Сначала сделаем бинпоиск по ответу. Теперь dp[i][j][k] — минимальное количество коровников, необходимое для того, чтобы в поддереве вершины i (рассмотрены только первые k сыновей вершины i) все непокрытые вершины были на расстоянии не более j от корня, либо, если j < 0, была фиксированная вершина такая, что d — maxd = j (d — расстояние до этой фиксированной вершины, maxd — текущий ответ). Тогда переход — это добавление новой ветки. Его можно просто делать за O(maxd) для одного состояния. Но я предположу, что умею делать этот переход за O(1).

Можно посчитать другую динамику dp2[i][j][k] — минимальная функция предыдущей динамики, такая, что нам понадобилось j коровников. (i и k не меняют роли). Тогда, можно заметить, что k * ans <= 2*n и считать динамику, которая считается быстрее. Тогда мы получим асимптотику O(n sqrt(n) log(n)).

Но, даже если понять, как делать переход за O(1) (это, вроде бы, возможно если разобрать несколько случаев), это решение все равно очень неприятное.

Есть ли в этой задаче что-то проще и с меньшим количеством случаев?