Изменения
→Ассимптотика
Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем LCA.
===Ассимптотика===Очевидно, что для * '''Память''': Для реализации алгоритма требуется <tex>O(n) </tex> памяти. * '''Препроцессинг''': Heavy-light декомпозиция строится за O(n). * '''Запросы''': По свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более <tex>log(n) </tex> путей. Значит время выполнения запроса также <tex>O(log(n))</tex>.
==См. также==
