36
правок
Изменения
→Псевдокод
Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.
*<tex>p[i][v]</tex> - i-тый двоичный подъем в предка вершины <tex>v</tex>
*way[v] - путь, проходящий через данную вершину
*num[v] - номер данной вершины на пути
*ladder[path][i] - возвращает i-тую вершину на пути path
'''function''' LA('''int''' v,'''int''' k):
'''int''' n = h(v); ''<font color="green">// получаем глубину вершины <tex>v</tex></font>''
n = n - k; ''<font color="green">// на столько необходимо подняться до ответа</font>''
i = <tex>\log_2 n</tex>;
v = p_ip[i][v] ''<font color="green">// делаем максимально большой прыжок вверх</font>''
i = n - i; ''<font color="green">// на столько осталось еще подняться</font>''
'''return''' ladder[way[num_on_wayv]][num[v] - i]; ''<font color="green">// так как теперь <tex>v</tex> и ответ находятся на одном пути</font>''
=== Доказательство корректности ===
