DP на дереве по времени с движущимися запретами — задача «Из Казани с любовью» РАЗБОР

Источник задачи: региональный этап Олимпиады им. М.В. Келдыша, 2025, задача E.

Что дано

Город представлен неориентированным деревом из $n$ вершин (связный граф без циклов, ровно $n-1$ рёбер). Главный герой Марат живёт в вершине $x$ и хочет добраться до работы в вершине $y$. Кроме него по городу движутся $m$ врагов: для каждого врага $i$ указана его домашняя вершина $a_i$ и рабочая вершина $b_i$.

Время дискретное: в момент $t = 1$ все одновременно выходят из своих домов. В каждый следующий момент времени каждый участник либо остаётся в текущей вершине, либо переходит в соседнюю по ребру. Враги движутся по кратчайшему пути от $a_i$ к $b_i$ (путь в дереве определён однозначно): если длина пути — $k$ рёбер, то в моменты $1, 2, \ldots, k+1$ враг $i$ последовательно посещает вершины пути, а после момента $k+1$ он остаётся в $b_i$.

Марат должен избегать встречи с врагом. Встречей считается любая из двух ситуаций в один и тот же момент времени: (1) Марат и какой-то враг находятся в одной вершине, либо (2) Марат идёт по ребру $u \to v$, а какой-то враг в этот же такт идёт по ребру $v \to u$ в противоположном направлении.

Требуется найти минимальный момент времени, в который Марат может оказаться в вершине $y$, не нарушив запрет встреч. Если такого момента не существует — вывести -1.

Ограничения

• $2 \leq n \leq 10^5$
• $1 \leq m \leq 100$
• $1 \leq x, y \leq n$, $x \neq y$; все $a_i, b_i$ — вершины дерева.

Формат ввода

Первая строка — четыре числа $n$, $m$, $x$, $y$ через пробел. Следующие $n - 1$ строк — рёбра дерева, по паре вершин в каждой. Следующие $m$ строк — пары $a_i$, $b_i$ для каждого врага.

Формат вывода

Одно целое число — минимальный момент времени прибытия Марата в $y$, либо -1, если задача неразрешима.

Пример 1 руками

4 1 1 4
1 2
3 4
4 1

Дерево: рёбра (1, 2), (3, 4), (4, 1). Марат: $x = 1 \to y = 4$. Один враг: $a = 4 \to b = 1$.

Дерево выглядит так (корнем в 1): 1 — 2, 1 — 4, 4 — 3.

Кратчайший путь Марата 1→4: длина 1 (одно ребро). Путь врага 4→1: тоже 1. В момент 1 оба выходят, в момент 2 Марат в 4, а враг — в 1. Ничего не встречают: вершина в момент 2 у них разная. Но если они шли по одному ребру в противоположных направлениях, это встреча на ребре (Марат 1→4, враг 4→1 — то же ребро).

Условие говорит «могут встретиться на ребре». Значит это встреча, и Марату нельзя идти. Надо другой путь.

Ответа нет «Марат остаётся»? Нет, ему надо дойти до 4. Кратчайший путь ровно такой — через ребро (1, 4). Придётся подождать, пока враг пройдёт.

В момент 1 враг в 4. В момент 2 враг в 1. В момент 3 враг дошёл до работы и больше не движется. С момента 3 Марат может идти: ребро (1, 4) свободно. Ответ: Марат стоит в 1 до момента 3, в момент 4 он в 4. Ответ 4. ✓

Пример 3

9 2 1 9
1 2
2 3
3 4
3 5
5 6
6 7
6 8
8 9
9 1
7 1

Дерево — «цепочка с веткой». Враги: $1 \to 9$ и $7 \to 1$. Марат: $1 \to 9$.

Первый враг идёт по кратчайшему пути 1→...→9 (длина 5: 1-9). Нет, проверим: путь 1→9 прямой, ребро 9 1 есть. Но вершина 9 подключена к 8 (ребро 8 9), а ребро 9 1... по списку рёбер: 1 2, 2 3, 3 4, 3 5, 5 6, 6 7, 6 8, 8 9, 9 1, 7 1. Есть ребро (9, 1). Значит 1 и 9 — соседи. Тогда дерево имеет ≥ 9 вершин и уже ≥ 10 рёбер — не может быть дерево.

Постой, $n - 1$ рёбер в дереве, для $n = 9$ — 8 рёбер. А у нас в примере 9 рёбер. Это не дерево.

Видимо в PDF отображение съехало, и «9 1», «7 1» — это описание врагов, а не рёбер. Перечитаем формат: «$j$-я из следующих $n-1$ строк содержит $v_j$ и $u_j$ — концы $j$-го ребра... $i$-я из следующих $m$ строк содержит $a_i$ и $b_i$».

Значит: 8 строк рёбер (1-2, 2-3, 3-4, 3-5, 5-6, 6-7, 6-8, 8-9), потом 2 строки врагов (9 1 = $a_1=9, b_1=1$; 7 1 = $a_2=7, b_2=1$). Но в примере $x = 1, y = 9$.

Первый враг идёт 9→...→1 (длина 5: 9-8-6-5-3-2-1, 6 рёбер? Или другой путь? Путь в дереве уникален: 9-8-6-5-3-2-1 = 6 рёбер, значит длина 6).

Второй враг 7→1: 7-6-5-3-2-1 = 5 рёбер, длина 5.

Ожидаемый ответ 10. Марат идёт 1→...→9, это тот же путь в обратную сторону: 1-2-3-5-6-8-9 = 6 рёбер, длина 6. Если бы враг не мешал, ответ был бы 7 (момент 7: в момент 1 выходит, момент 2 в 2, ..., момент 7 в 9). Но Марат идёт навстречу врагу, который возвращается (нет, враг идёт 9→1, а Марат 1→9 — они встретятся где-то посередине). Значит Марату приходится ждать.

Это и есть ключевая сложность: нужно точно моделировать, где оба будут в каждый момент.

---

Идея решения

Формализация

Марат — агент, движущийся по дереву. В каждый момент $t$:

• Он в какой-то вершине.
• Враги — точно в определённых позициях (функция от $t$ и пути врага).

Состояние Марата — $(\text{вершина}, t)$. Переходы: остаться или пойти в соседа. Запреты:

1. Запрет вершины: если в момент $t$ в вершине $v$ есть хоть один враг — Марат не может быть в $v$.
2. Запрет ребра: если Марат идёт из $u$ в $v$ в переходе $t \to t+1$, а какой-то враг идёт из $v$ в $u$ в тот же такт — нельзя.

DP по $(v, t)$

$dp[v][t] = 1$, если Марат может быть в вершине $v$ в момент $t$ (без нарушений).

• База: $dp[x][1] = 1$.
• Переход: $dp[v][t+1] = 1$ тогда и только тогда, когда:
  • в момент $t+1$ нет врага в $v$;
  • существует $u \in N(v) \cup \{v\}$ такой, что $dp[u][t] = 1$ и переход $u \to v$ не конфликтует с врагом (если $u \neq v$, то ни один враг не делает ход $v \to u$ в такт $t \to t+1$).

Ответ: минимальное $t$, для которого $dp[y][t] = 1$.

Ключевое ограничение ответа

Лемма. Если ответ $\neq -1$, то он не превосходит $2N + 1$.

Доказательство. Пусть оптимальный путь — $s_1 = x, s_2, s_3, \ldots, s_k = y$. Дерево имеет $N$ вершин, любой путь врага не длиннее $N - 1$ рёбер — значит к моменту $N + 1$ все враги уже дошли до своих работ и больше не двигаются. Если Марат в момент $N + 1$ находится в какой-то вершине $s_{N+1}$, то дальше он просто идёт по кратчайшему пути к $y$, который имеет длину $\leq N - 1$. Итого момент прибытия $\leq (N + 1) + (N - 1) = 2N$, а с запасом на шаг стояния — $2N + 1$. □

Значит в DP достаточно перебрать $t$ от $1$ до $2N + 1$.

Сложности вариантов

В этой статье — прямолинейный DP: пересчитываем $dp$ до $t = 2N + 1$. Для $N = 10^5$ это не пройдёт по памяти / времени в явном виде (нужен $O((N+M) \cdot N)$ через аккуратное обновление множества достижимых вершин — переход от хранения полной матрицы $dp[v][t]$ к обработке только вершин, достижимых в текущий момент, с ленивым применением запретов). Но идея одна и та же.

---

Решение: псевдокод (для малых N)

читать n, m, x, y
построить дерево (список смежности)
читать врагов — для каждого врага i найти путь в дереве от a_i к b_i (BFS)
предпосчитать occupation[v][t] — множество t, когда в v есть хоть один враг
предпосчитать forbidden_edge[u][v][t] — запрет перехода u→v в такт t→t+1 (если враг идёт v→u)

dp[x][1] = true
для t = 1..2n:
    для v = 1..n:
        если не dp[v][t]: continue
        # остаться в v
        если в момент t+1 в v нет врага: dp[v][t+1] = true
        # перейти в соседа
        для каждого соседа u:
            если в момент t+1 в u нет врага
              и переход v→u в такт t→t+1 не запрещён:
                dp[u][t+1] = true

найти минимальное t, для которого dp[y][t] = true
если не нашли — вывести -1

---

Код решения (для частичных баллов)

Ограничение: $O(N \cdot T \cdot \deg)$ — для $N = 100$ работает; для $N = 10^5$ уже нет. Для полного решения нужна оптимизация — см. раздел ниже.

---

Проверим на первом примере

4 1 1 4
Рёбра: (1,2), (3,4), (4,1)
Враг: (4, 1)

Дерево: 1 — 2, 1 — 4, 4 — 3.

Путь врага 4→1: [4, 1]. В момент 1 он в 4, в момент 2 в 1. occupation[4] = {1}, occupation[1] = {2}. edge_trans[(4, 1)] = {1} — враг идёт 4→1 в такт 1→2.

Марат в момент 1 в вершине 1. В момент 2 хочет в 4. Проверка:

• occupied(4, 2)? 2 in occupation[4] = {1}? Нет.
• edge_blocked(1, 4, 1)? Проверяем 1 in edge_trans[(4, 1)]. Да! — значит переход 1→4 в такт 1→2 блокирован.

Значит в момент 2 Марат не может быть в 4. Может остаться в 1? occupied(1, 2) = 2 in {2} = да. Нельзя. Марат не может остаться — там будет враг.

Может ли Марат в момент 2 уйти в 2? occupied(2, 2) = нет. edge_blocked(1, 2, 1)? Враг идёт 2→1 в такт 1→2? Нет. Можно. Марат в 2 в момент 2.

В момент 3: враг в своей работе (1), путь закончен в момент 2. occupation[1] = {2}, так что в момент 3 в 1 никого. Марат может вернуться: dp[1][3] = True.

В момент 4 Марат идёт 1→4: occupied(4, 4) = нет, edge_blocked(1, 4, 3) = нет. Достиг. Ответ 4. ✓

---

Крайние случаи

1. $x = y$. Марат уже на работе. Ответ 1, если в момент 1 в $y$ нет врага. Но враг в момент 1 в $a_i$ — если $y = a_i$ для какого-то $i$, нужно подождать.

2. Нет врагов ($m = 0$). Ответ — просто расстояние от $x$ до $y$ плюс 1.

3. Невозможно. Ответ $-1$. По лемме, если за $2N + 1$ момент не получилось — значит невозможно.

4. Враг стоит в точке назначения Марата. $b_i = y$ — враг там в момент $k_i$ (он пришёл). После этого он стоит? В условии явно: «$i$-м врагом только в моменты времени $2, 3, \ldots, k$», то есть после момента $k$ враг уже не встречается (он «исчез»). Удобно: занятость $y$ заканчивается, как только последний враг дойдёт.

5. Враги могут стоять в $y$ одновременно в момент 1. Марат начинает в $x$, не в $y$ (если $x \neq y$). Проверяется в базе DP.

---

Типичные ошибки

1. Забыть про встречу на ребре. Самая частая ошибка. Решение «просто DP по вершинам без проверки рёбер» пройдёт только первый пример.
2. Считать, что враг «застывает» в $b_i$ после прихода. Условие явно говорит, что после момента $k$ враг не встречается. То есть он не занимает вершину $b_i$ дольше.
3. Не ограничить $t$. Без лемма «ответ ≤ $2N + 1$» DP может идти бесконечно.
4. Не сжимать множество достижимых вершин. В полном решении вместо dp[v][t] хранят S_t — множество вершин, куда Марат может попасть в момент $t$. $S_{t+1}$ пересчитывается из $S_t$ за ~$O(M)$ амортизировано.

---

Сложность

• Наивный DP: $O(N \cdot T \cdot \text{deg}) = O(N^2)$. Подгруппы 1–3, до 55 баллов.
• Полное решение: $O(N \cdot M)$ через аккуратное поддержание множества $S_t$ с учётом «кандидатов» (вершин, которые нельзя упустить). Детали технически объёмны и выходят за рамки этой статьи.

---

Что ещё полезно потренировать

• Codeforces 1037D «Valid BFS?» — BFS / DFS по дереву, базовый навык.
• Codeforces 1328E «Tree Queries» — запросы на пути в дереве.
• Codeforces 1294F «Three Paths on a Tree» — диаметр дерева + максимизация.
• Codeforces 1296E2 «String Coloring (hard)» — DP по массиву с запретами (идея DP по времени).

Общий мотив: дерево + DP по вершине и моменту / слою — базовая техника, на которой строятся более сложные задачи.

---

Итого

• Модель: DP dp[v][t] = может ли Марат быть в $v$ в момент $t$; переходы учитывают занятые вершины и запреты рёбер.
• Ключевая лемма: ответ либо $-1$, либо $\leq 2N + 1$.
• Наивное решение: $O(N^2 + N \cdot M)$, подгруппы 1–3.
• Полное решение: $O(N \cdot M)$ через ленивое обновление множества достижимых вершин.
• Ловушки: встреча на ребре, границы времени, обработка «враг пришёл на работу и пропал».