В этой задаче нам нужно искать <<кратчайшие>> пути в графе, но рёбра на графе не являются взвешенными; время перехода по ребру из $u$ в $v$ зависит от момента времени, в который мы это делаем. Несмотря на это, идеи из стандартных алгоритмов всё ещё применимы\footnote{
Более формально, для алгоритмов поиска расстояний из одной вершины до всех остальных требуется выполнение трёх свойств:
\begin{itemize}
\item Монотонность: $\text{Len}(\text{path}) \le \text{Len}(\text{path} + e)$
\item Консистентность: если $\text{Len}(\text{path}_1) = \text{Len}(\text{path}_2)$, то $\text{Len}(\text{path}_1 + e) = \text{Len}(\text{path}_2 + e)$
\item Оптимальность начала: если $\text{Len}(\text{path}_1) \le \text{Len}(\text{path}_2)$, то $\text{Len}(\text{path}_1 + e) \le \text{Len}(\text{path}_2 + e)$
\end{itemize}
}.

Пусть в момент времени $T$ с человеком $u$ провели воспитательную беседу, и мы хотим понять, когда с его соседом $v$ проведут воспитательную беседу. Другими словами, мы хотим понять время перехода по ребру из $u$ в $v$ в момент времени $T$.

Нам нужно найти первый из моментов времени $a_v, a_v + t_v, \dots$, который при этом позже $T$. Сдвинем нашу шкалу времени назад на $a_v$. Теперь нам нужно найти минимальное число, кратное $t_v$, большее $T - a_v$. Это будет

$$\left\lceil\frac{T - a_v + 1}{t_v}\right\rceil \cdot t_v$$

Таким образом, мы перейдём в вершину $v$ в момент времени

$$a_v + \max\left(0, \left\lceil\frac{T - a_v + 1}{t_v}\right\rceil \cdot t_v\right)$$

Взяв $T = \text{dist}_u$, мы можем пересчитать этой величиной $\text{dist}_v$.

В подгруппе 2 граф является деревом, то есть до каждой вершины существует единственный простой путь.

В подгруппе 3 время перехода по ребру всегда равно $1$, поэтому мы можем использовать обычный поиск в ширину.

В подгруппе 5 время перехода по ребру не больше $20$, поэтому мы можем использовать поиск в ширину с несколькими очередями (1-K BFS).

В подгруппах 7 и 8, а также в полном решении нужно применить алгоритм Дейкстры.