74
правки
Изменения
→Препроцессинг
Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из корня, который будет вычислять значения следующих величин:
#Cписок глубин посещенных вершин <tex>d</tex>. Глубина текущей вершины добавляется в конец списка при входе в данную вершину, а также после каждого возвращения из её сына.
#Список посещений узлов <tex>\mathtt{vtx}</tex>, строящийся аналогично предыдущему, только добавляется не глубина а сама вершина.
#Значение функции <tex>\mathtt{I}[u]</tex>, возвращающей любой индекс в списке глубин <tex>d</tex>, по которому была записана глубина вершины <tex>u</tex> (например на момент входа в вершину).
