\Section{Минимум на пути в дереве}{15 марта}{Илья Кайсин}

\Subsection{Постановка задачи}

Для построения минимального остовного дерева за линейное время нужно научиться искать минимум на пути в дереве за $\O(1)$. 

Пусть дано дерево из $n$ вершин и $m$ запросов. Хочется ответить на все запросы за $\O(m + n)$ в offline.

\Subsection{Обзор существующих медленных решений}

\subsubsection{Centroid decomposition}

В каждом поддереве centroid decomposition посчитаем минимумы от каждой вершины до корня (центроида). Для ответа на запрос достаточно узнать LCA в дереве centroid decomposition. Сложность решения --- $\O(m \cdot \t{LCA} + n \log n)$. Если искать $LCA$ алгоритмом Фарах-Колтона и Бендера, получим $\O(m + n \log n)$.

\subsubsection{Двоичные подъёмы}

Та же идея, что и при поиске LCA методом двоичных подъёмов. Но для каждой вершины $v$ помимо предка, находящегося на $2^k$ рёбер выше (\t{p[k][v]}), подсчитаем ещё и минимум на пути $\t{v} \leadsto \t{p[k][v]}$. Тогда вместе с $\t{LCA(u, v)}$ мы сможем подсчитать и минимумы на путях $\t{u} \leadsto \t{LCA}$ и $\t{v} \leadsto \t{LCA}$. Асимптотика --- $\O(m \log n + n)$, online.

\subsubsection{dfs с деревом отрезков}

Решим задачу в offline. Разобьём каждый запрос на два вертикальных ($\O(m \cdot \t{LCA})$). Запомним для каждой вершины, являющейся нижним концом вертикального запроса, все связанные с ней запросы. Будем обходить дерево dfs-м, поддерживая стек весов рёбер на пути до корня. В этом стеке нужно узнавать минимум на куске верхних элементов. Для этого заменим стек на дерево отрезков. Асимптотика --- $\O(m \cdot \t{LCA} + (m + n) \log n)$, offline.

\Subsection{Алгоритм с СНМ}

Как обычно, разобьём каждый запрос на два вертикальных. Теоретически для этого будем использовать алгоритм Фарах-Колтона и Бендера, а на практике --- алгоритм Тарьяна.

В данном алгоритме мы не можем пользоваться СНМ как чёрным ящиком, нужно взаимодействовать со внутренней структурой. В СНМ с эвристикой сжатия путей будем хранить вершины дерева. Каждое множество будет представлять собой связное множество вершин дерева, корнем множества в СНМ всегда будет корень связного множества в дереве. Изначально каждая вершина --- отдельное множество. Для каждой вершины \t{v} будем поддерживать \t{w[v]} --- минимум на пути в дереве от неё до её родителя в СНМ (этот путь будет в дереве вертикальным).

Операция \t{Get(v)} возвращает минимум на пути в дереве от \t{v} до представителя (в СНМ) множества, содержащего \t{v}. Псевдокод приведён ниже. \t{p[v]} --- родитель в СНМ, \t{w[v]} --- минимум на пути $\t{v} \leadsto \t{p[v]}$ в дереве.

\begin{code}
Get(v) {
	if (v == p[v])
		return w[v];
	Get(p[v]); // w[p[v]] has changed
	w[v] = min(w[v], w[p[v]]);
	p[v] = p[p[v]]; // path compression
	return w[v];
}
\end{code}

Заметим, пока мы нигде не делали Join, это будет происходить в процессе обработки запросов. Для каждой верхней вершины вертикального запроса запомним все связанные с ней нижние вершины: \t{ListD[U]}. Отсортируем все вершины снизу вверх (например, в порядке, обратном порядку посещения dfs-м, или по убыванию глубины, главное, чтобы для каждого поддерева корень находился в отсортированном массиве после всех остальных вершин этого поддерева). Разумеется, сортируем за линейное время. 

Ниже приведён псевдокод обработки запросов. \t{Sorted} --- отсортированный снизу вверх массив вершин, \t{parent[v]} --- родитель \t{v} в исходном дереве.

\begin{code}
for (U in Sorted) {
	for (D in ListD[U]) {
		Answer = get(D);
	}
	p[u] = parent[u]; // Join
}
\end{code}

В данном варианте кода предполагается, что взвешены вершины, а не рёбра, и \t{w[v]} инициализируется весом вершины $v$.

Если взвешены рёбра, то \t{w[v]} изначально равно $+\infty$, и в код обработки запросов добавится ещё одна строчка:

\begin{code}
for (U in Sorted) {
	for (D in ListD[U]) {
		Answer = get(D);
	}
	p[u] = parent[u]; // Join
	w[u] = weight[u];
}
\end{code}

\t{weight[u]} --- вес ребра из \t{u} в \t{parent[u]} в исходном дереве.


Как же работает этот код? Легко видеть, что сохраняется такой инвариант: в момент, когда мы пришли в вершину \t{U}, всё поддерево с корнем \t{U} объединено в одно множество в СНМ, и \t{U} --- представитель этого множества. Поэтому операции \t{Get(D)} отработают корректно.

Поскольку в СНМ используется лишь одна эвристика, время работы алгоритма --- \\ $\O((n + m) \log n)$, но на практике работает очень быстро. Утверждается, что можно получить линейную асимптотику, если добавить ранговую эвристику (решив возникшие при этом проблемы отложенным Join-м) и метод четырёх русских.
