coder.ua пишет:Спасибо, но я не пойму зачем нам сумма длин путей до LCA. Возможно таким образом можно найти максимальное ребро на цикле или я что-то неправильно понимаю понимаю?
В плане - сумма длин это будет сумма ребер цикла. Я когда писал, забыл о максимальном ребре 
. Для его нахождения нужно просто найти максимум из всех ребер от А до LCA и от B до LCA.
Чтобы сложность вышла линейной, можно после нахождения LCA, запустить дфс и для каждой вершины A в нем перебрать все ребра инцидентные ей, которые не вошли в миностов, для каждого второго конца B взять уже найденный LCA и затем посчитать максимум среди всех ребер от вершины до LCA. Так как мы находимся в дфсе, список вершин, в которых мы побывали но еще не вышли из рекурсии образует путь, причем LCA и A лежат в этом пути, а A является последней вершиной в нем. Можно в стеке хранить возрастающую последовательность номеров ребер и при спуске в рекурсию (добавлению нового ребра) удалять ребра из вершины стека до тех пор, пока они не превышают данное. Затем, максимум от LCA до A сводится к поиску номера i в стеке, такого что i-е ребро лежит ниже на пути чем LCA, а i-1 -е ребро уже выше. Очевидно, что это ребро и будет искомым максимумом. Можно, конечно, это искать бинпоиском, но так как за NlogN можно и проще сделать, я расскажу как это делать за O(1) в среднем.
Когда ребро выпихивается другим ребром из стека, сохраним для него ссылку на то ребро, которое его выпихнуло. Затем, когда выпихнется и то ребро - мы должны изменить ссылку. Это можно делать системой непересекающихся множеств.
Теперь мы научились извлекать максимум и спускаться ниже в рекурсию. Остается вопрос - что делать, когда нам нужно подниматься? При спуске мы сделали О(К) изменений памяти, значит, мы за О(К) можем их всех откатить, вернув в стек ребра и изменив состояние системы непересекающихся множеств. Таким образом, получаем алгоритм, который за О(E) в оффлайне находит все максимумы ребер от A до LCA(A,B), где B - второй конец ребра невошедшего в миностов, инцидентного A.
Если же хочется O(NlogN) - можно просто для каждой вершины предпосчитать максимальное ребро до первой, второй, четвертой и т.д. вершин на пути от данной вершины к корню дерева.