Изменения

Рассмотрим рёбра вне остова в любом порядке. Очередное обозначим <tex>e = (u, v)</tex> вне остова в любом порядке. Рассмотрим максимальное ребро на пути <tex>u</tex> и <tex>v</tex> внутри остова:*Если его вес совпадает с весом ребра, то при добавлении ребра в остов, мы получим остов с циклом на котором несколько рёбер имеют одинаковый вес, значит мы можем удалить любое из них и остовное дерево будет всё ещё минимальным, это нарушает уникальность дерева. На этом алгоритм завершается и по критерию Тарьяна мы можем сказать, что в графе можно построить несколько остовных деревьев.

Искать максимальное ребро на пути <tex>u</tex> и <tex>v</tex> в дереве мы можем при помощи алгоритма минимального общего предка(LCA), используя [[метод двоичного подъема]].Подвесим дерево за любую вершину, обозначим её за <tex>root</tex>. Построим LCA. Построим массив <tex>Dp</tex>, используя дополнительный массив <tex>up</tex> из LCA. <br><tex>dp[i][j]= \begin{cases}0 & j = 0,\\max(dp[up[i][j - 1]][j - 1], dp[i][j - 1]) & j \: \textgreater \: 0.\end{cases}</tex> <br> Храним максимальный вес ребра на пути <tex>i</tex> и <tex>root</tex>, где <tex>i -</tex> номер вершины, <tex>j -</tex> степень подъёма(как в LCA). При запросе рассмотрим два случая:*Путь ребра содержит корень. ЗаметимПосле рассмотрения всех рёбер, если разделить путь на две частимы не нашли ребро вне остова, то при добавлении которого создаётся цикл с максимальным ребром будет максимальное среди меньших путей. Разобьём путь <tex>u</tex> таким же как и <tex>v</tex> на пути <tex>u</tex> и <tex>rootv</tex>, <tex>v</tex> то в графе нету другого остовного дерева и <tex>root</tex>наше дерево уникально. Найдём Искать максимальное ребро на пути <tex>u</tex> и <tex>root</tex>, <tex>v</tex> и <tex>root</tex>, максимальное из них и будет являться ответом.*Путь ребра не содержит корень. Будем подниматься из нижней вершины до высокой используя массив <tex>Dp</tex>. Какая из вершин выше узнаём используя функцию isUpper(в LCA используется)дереве мы можем при помощи [[Heavy-light декомпозиция|heavy-light декомпозиции]].

Построение минимального остовного дерева работает за <tex>O(N \log N)</tex>, нахождение максимального ребра за <tex>O(\log N)</tex>, максимальное количество рёбер вне остова не больше <tex>N</tex>, каждое ребро проверяется за <tex>O(\log N)</tex>. Построение LCA и дополнительного массива heavy-light декомпозиции работает за <tex>O(N \log N)</tex>, остов мы построим один раз, LCA heavy-light декомпозицию тоже один раз, каждое ребро мы не больше одного раза проверим на замену, сложность алгоритма <tex>O(N \log N)</tex>.