Отсортируем зараженные города по времени входа, удалим те, которые лежат в поддереве другого зараженного. Теперь нужно взять максимум расстояний от нашей вершины до всех хороших. Сгруппируем вершины по LCA с нашей. Такими LCA могут быть только предки нашей вершины.

Рассмотрим некоторого предка w нашей вершины v, не совпадающего с v. Если w плохая, то все её потомки тоже плохие, а значит в группе w нет хороших вершин. Теперь w хорошая. Пусть среди вершин, входящих в группу w вообще все вершины хорошие. Тогда нам нужно просто взять среди них вершину с максимальной глубиной. Для этого сделаем следующий прекальк. Для каждой вершины найдем две наиболее глубокие вершины в поддеревьях разных сыновей. Теперь для ребра (vu), идущего вверх, запомним самую глубокую вершину такую, что она потомок u, но не потомок v.

Теперь заметим, что среди предков v будет не более k+1 вершин не таких, как я описал в предыдущем абзаце. Каждую из этих k+1 вершин мы можем обработать отдельно, взяв максимум глубин по хорошим вершинам (хорошие вершины суммарно будут образовывать O(k) отрезков в эйлеровом обходе, поэтому достаточно завести ДО или sparse table на максимум глубины над эйлеровым обходом). Остальные вершины разобьются на O(k) вертикальных путей. Чтобы брать максимум на пути, построим двоичные подъемы на максимум функции deepest(v) - 2·h(v).

Получилось очень сумбурно, без бумажки сложно. Я надеюсь, разобраться можно. Более простая версия (с k=1) использовалась как подзадача в задаче I с Tsinghua U Deep Dark Fantasy Contest, Ptz Winter 17, Day 5.

А кто-нибудь сдал? У меня не стрессится :(

upd: Все норм, просто K ≥ 0 на самом деле.

A — динамика по подмаскам. Зависимости между гипотезами тоже лучше хранить в сжатом виде побитово

D — всегда нужно пытаться идти к дальней катапульте. Разные варианты будут только на первом шаге, это перебирается.

Почему никто не отвечает?

Пусть хотим узнать, достижима ли какая-то маска. Это можно сделать следующей динамикой:
dp[i][mask] — минимальное количество операций, за которое можно правильно построить первые i столбцов, чтобы в маске строк mask в i-ом столбце заканчивались горизонтальные операции (и возможно в каких-то еще строках).

При фиксированном i динамика представляет из себя функцию {0, ..., 2ⁿ - 1} → {0, ..., maxk + 1} и переходы зависят только от нее. Тогда можно посчитать динамику ans[i][func] -- количество масок, у которых dp[i] = func.

Всего функций не очень много, решение считает все ответы за ~ 0.3 секунды.

4 тур идет с 22 января по 1 февраля, уже прошло 3 дня со старта, а зайти возможности так и не появилось, как и хоть какой-нибудь реакции от организаторов.

Что за hard life?