Изменения
Нет описания правки
== Алгоритм ==
Подвесим наше дерево за любую вершину, и запустим обход в глубину из её.
Ответ на каждый запрос мы найдём в течении этого <tex>dfs'a</tex>. Ответ для вершин <tex>v</tex>,<tex>u</tex> находится, когда мы уже посетили вершины <tex>u</tex>, а в <tex>v</tex> обработали всех сыновей и собираемся выйти из неё.
Зафиксируем момент, мы собираемся выйти из вершины <tex>v</tex> (обработали всех сыновей) и хотим узнать ответ для пары <tex>v</tex>,<tex>u</tex>.
Тогда заметим что ответ - это либо вершина <tex>v</tex>, либо какой-то её предок. Значит нам нужно найти предок вершины <tex>v</tex>, который является предком вершины <tex>u</tex> с наибольшей глубиной. Заметим, что при фиксированном <tex>v</tex> каждый из предков вершины <tex>v</tex> порождает некоторый класс вершин <tex>u</tex>, для которых он является ответом (в этом классе содержатся все вершины которые находятся "слева" от этого предка).
Будем поддерживать массив <tex>ancestor[v]</tex> - представитель множества в котором содержится вершина <tex>v</tex>.
Для каждого класса мы образуем множество, и представителя этого множества.
Когда мы приходим в новую вершину <tex>v</tex> мы должны добавить её в новый класс (<tex>ancestor[v] = v</tex>),а когда просмотрим всё поддерево какого-то ребёнка, мы должны объединить это поддерево с нашим классом (операция <tex>union</tex>), и не забыть установить представителя как вершину <tex>v</tex> (в зависимости от реализации это может быть какая-то другая вершина).
Зафиксируем вершины <tex>v</tex>, и выделим путь от корня до этой вершины. Теперь все рёбра "левее" этого пути уже добавлены в <tex>dsu</tex>, все рёбра правее — ещё не обработаны, а все рёбра на пути — обработаны, но в <tex>dsu</tex> ещё не добавлены, так как в <tex>dsu</tex> мы добавляем при выходе.
К самой первой вершине этого пути, до которой мы доберёмся, если будем просто подниматься. Очевидно, это и есть <tex>lca</tex>.
После того как мы обработали всех детей вершины <tex>v</tex>,мы можем ответить на все запросы вида (<tex>v</tex>,<tex>u</tex>) где <tex>u</tex>-уже посещённая вершина.Нетрудно заметить что ответ для <tex>lca(v,u) = ancestor(find(u))</tex>.Так же можно понять что для каждого запроса это условие(что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.
[[file:mytree.png|500px|разные цвета-разные классы,а белые вершины ещё не просмотренные в dfs]]
=== Реализация ===
}
unite (int a, int b,int new_ancestor) {
a = dsu_get (a);
b = dsu_get (b);
if (not visited[u])
dfs(u);
union(v,u,v);
for (i = 0; i < query[v].size; i++)
if (visited[query[v][i]])
