Ещё задача на дереве

Вроде жадно можно. Просто пускаем обход по дереву, как бы идём от листьев вверх, и как только оказывается, что мы в текущей вершине обязаны заражать, то заражаем. Т.е. делаем dfs, который возвращает расстояние до самого далёкого незаражённого потомка, и если в текущей вершине это значение получилось равно k - заражаем её, иначе - нет.

Когда заражаешь какую-то клетку, возвращаешь -k. Т.е. возвращаемое значение может быть отрицательным, и надо написать обход так, чтобы с отрицательными числами всё было адекватно тоже.

Нет, насколько я помню, вполне там можно обойтись без пометок.

Кажется, что незачем передавать в dfs значение, пришедшее "сверху": ведь в таком решении то, что происходит выше текущей вершины, - не особенно-то и важно. Это решение заражает вершины в жадном порядке, каждый раз заражая только действительно необходимую вершину. Поэтому передавать ничего не надо, а просто надо посмотреть: если мы после запуска dfs из всех потомков видим, что один какой-то потомок вернул отрицательное число, превосходящее по модулю все положительные числа из других потомков - то все эти положительные потомки можно мысленно "удалить".

UPD:

Надо не -1, а -k, потому что это важно, на каком именно расстоянии произошло ближайшее снизу заражение.