Изменения

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

Heavy-light декомпозиция

120 байт добавлено, 00:30, 9 мая 2016
Вычисление LCA
====Вычисление LCA====
Будем Пусть требуется найти LCA для двух вершин. Для этого будем рекурсивно подниматься от этих вершин в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, <tex>v</tex>.
Пусть <tex>a</tex> и <tex>b</tex> {{---}} вторые вершины путей, содержащих вершины <tex>u</tex> и <tex>v</tex> соответственно. Важно заметить, что любая вершина, помимо корня дерева является некорневой вершиной какого-либо другого пути, поэтому такие <tex>a</tex> и <tex>b</tex> всегда существуют.
Анонимный участник

Навигация