Переформулируем задачу. Дан неориентированный граф, требуется для каждого ребра определить максимальный его вес, при котором оно будет входить в минимальное остовное дерево.
Задача разбивается на несколько похожих случаев. Проще всего начать со случая ребер, которые не входят в MST. Для таких ребер достаточно заранее построить произвольное MST, после чего воспользоваться леммой о безопасном ребре: чтобы ребро входило в MST, оно должно быть одним из минимальных в каком-то разрезе графа, разделяющем концы этого ребра.
Иными словами, построим MST и обозначим множество ребер в нем $$$M$$$. Рассмотрим какое-то ребро $$$e \not\in M$$$. Если добавить это ребро в MST, мы получим множество $$$M \cup \{e\}$$$, в котором есть цикл, проходящий по $$$e$$$. Чтобы существовал минимальный остов, содержащий $$$e$$$, как следствие из леммы о безопасном ребре, необходимо и достаточно, чтобы на цикле существовало ребро веса не меньше $$$p_e$$$. Таким образом, ответ для $$$e \not\in M$$$ — это вес максимального ребра на образующемся цикле, который можно найти с помощью двоичных подъемов и lca за время $$$\mathcal{O}(\log n)$$$.
В случае с ребрами $$$e \in M$$$ все аналогично: до какого-то момента можно просто увеличивать вес ребра, но в какой-то момент появится «замена», которую можно добавить вместо $$$e$$$, уменьшив вес дерева. Пусть при удалении $$$e$$$ дерево $$$M$$$ разбивается на $$$M_1$$$ и $$$M_2$$$. Тогда заметим, что $$$p_e = \min\limits_{u \in M_1, v \in M_2, (uv) \not\in M} w_{uv}$$$ — это вес минимального ребра между $$$M_1$$$ и $$$M_2$$$, на которое можно заменить удаляемое $$$e$$$. При большем весе $$$e$$$ эта замена приводит к уменьшению веса остова, что означает, что $$$e$$$ никакому минимальному остову не принадлежит.
Осталось эту величину посчитать для каждого $$$e \in M$$$. Для этого есть два способа:
При таком алгоритме каждое ребро будет ровно один раз добавлено в какое-то множество и ровно один раз удалено, поэтому в сумме это займет $$$\mathcal{O}(m \log m)$$$ времени. А объединения множеств с помощью техники small-to-large займут в сумме $$$\mathcal{O}(m \log^2 m)$$$ времени.