74
правки
Изменения
м
→Препроцессинг
=== Препроцессинг ===
Для каждой вершины <tex>T</tex> определим глубину с помощью следующей рекурсивной формулы:
:<tex>\mathrm{depth}(u)= \begin{cases}0 & u = \mathrm{root}(T),\\\mathrm{depth}(v) + 1 & u = \mathrm{son}(v)
\end{cases}.</tex>
Ясно, что глубина вершины элементарным образом поддерживается во время обхода в глубину.
