Improve minimum spanning tree with new edge, with better running time than O(|V|)?
Using Heavy path decomposition.

The key idea is to partition all edges into heavy edges and light edges.
Consider tree edge from parent node X to child node Y:


heavy edge: size of sub tree Y is at least half of the size of sub tree X;
light edge: size of sub tree Y is smaller than half of the size of sub tree X;


There are at most $O(\log |V|)$ heavy paths (path with only heavy edges) from any leaf to root. Maintaining each heavy path using segment tree or balanced BST, and converting MST into tree of heavy paths, one can query the heaviest edge $e_{max}$ between any two vertices $u$,$v$ in $O(\log |V|)$. 

Another method is using Link cut tree which handles each query in $O(\log |V|)$ amortized time complexity. This can also handle the case that each query is applied to the result of previous implement.