Решение с помощью Эйлерова обхода: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «Выпишем эйлеров обход дерева (3 вариант - выписывая вершину каждый раз, как мы в нее попад...»)
 
Строка 8: Строка 8:
  
 
1)[[Sparse Table]]
 
1)[[Sparse Table]]
2)[[Корневая]]
+
 
3)[[Дерево Отрезков]]
+
2)[[Корневая Декомпозиция]]
 +
 
 +
3)[[Дерево отрезков]]

Версия 10:32, 27 ноября 2019

Выпишем эйлеров обход дерева (3 вариант - выписывая вершину каждый раз, как мы в нее попадаем). Заметим, что из всех вершин на отрезке от вершины $u$ до вершины $v$ наименьшее расстояние от корня будет иметь $lca(u, v)$, Докажем :

1) $lca(u, v)$ входит в отрезок, так как она содержится на пути между ними. 2) Весь отрезок содержится в поддереве $lca(u, v)$, так как мы не могли выйти из нее

Будем считать, что $tout_{u} <= tin_{v}$, если это не так свапнем вершины. Тогда давайте выпишем не только эйлеров обход, но и массив глубин вершин эйлерова обхода, тогда давайте найдем минимальное число на отрезке от $tout_{u}$ до $tin_{v}$, тогда вершина, которая соответствует минимуму на отрезке - $lca(u, v)$, Искать минимум на отрезке можно с помощью следующих структур

1)Sparse Table

2)Корневая Декомпозиция

3)Дерево отрезков