Изменения

Перейти к: навигация, поиск

Level Ancestor problem

390 байт добавлено, 15 май
Псевдокод
Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.
 <code> '''function'''LA('''int ''' v,'''int ''' k): '''int n'' ' n = h(v); ''<font color="green">//получаемглубину вершины <tex>v</tex></font>'' n = n - k; ''<font color="green">// на столько необходимо подняться до ответа</font>'' i = <tex>\log n</tex>; v = p_i[v] ''<font color="green">// делаем максимально большой прыжок вверх</font>'' i = n - i; ''<font color="green">// на столько осталось еще подняться</font>'' '''return''' way[num_on_way[v] - i]; ''<font color="green">//так как теперь <tex>v</tex> и ответ находятся на одном пути</font>''
</code>
Анонимный участник

Навигация