The problem gives a MST T and a series of Q queries, each one with a new edge e = {u, v} such that no edge between u and v exists in T. For every query, we have to improve T with e and print the new weight of T.
The best I can do is run a DFS (O(|V|)) to find the current path P between u and v, and find the heaviest edge 
in P. If 
, we improve T removing and inserting e. The overall running time for a test case is O(Q|V|).
Does anybody know an asymptotically faster algorithm for this problem?
Thanks in advance!
I know, it's called link/cut tree. It can solve the problem in O(Qlog|V|) online (and many other tree-related problems). I wouldn't call it easy to understand or implement, though. Not even talking about proof of time boundary.
Sorry, I don't understand. It's
for the whole test case??? It's like 
, but Q is not important? Is that it?
Oh, I get it. Each operation costs
. It's actually 
for a test case. Thanks! Very helpful!
Yep, I'm sorry, fixed that.
I finally implemented the DS, but I'm having trouble to augment it to support the query I need. I need something like
, the heaviest edge in the path from the root to u, and what vertices are incident to this edge. I'd appreciate any help!
You can take a look at these posts: original, follow-up (Russian only).
Tl;dr: one possible way of doing something with edges is to add artificial vertices on the middle of every edge and use them instead of edges, remaining vertices can be filled with some "neutral" value (like - ∞ in case of maximum) or just marked as "skip this vertex" (which is essentially the same).
Thanks! Good idea! Now I'm debugging my code, and I found that my link() operation is not working correctly, because it requires that one of the vertices to be the root of its tree. Do you know how to implement this makeroot(v) operation, or any other workaround to this problem? Thanks again for the help!
Edit: I saw that this makeroot(v) is actually called evert(v), but I can't find a good site/tutorial/code or whatever that I could understand... I saw the operation in Sleator's original paper, but I'm having too much trouble to understand...
Edit2: Ok, evert is just swapping childs in a whole splay tree. My code is now correct, but slow... Probably because evert needs lazy propagation to run in O(lg n), right?
Could you please provide a link to the code for the same?
OMG I can't remember the problem, sorry =(
I just want to point out that you are searching for a path in the MST, which itself has size of O(|V|), so the algorithm is actually O(Q * |V|) in total. I know it's not that significant but it was actually given as a problem in IOI long time ago, with the author solution being O(Q * |V|).
Indeed, trees have |E| = |V| - 1 = O(|V|)! But I was aware of that writing the post. I'll edit, thanks!
Do the same thing as in LCA algorithm, but save not only 1, 2, 4, 8... parents, but also maximum among 1, 2, 4, 8 edges on the path to the root. Then you can answer a query in logN. No link-cut trees!
And how do we update the LCA DS, removing an edge and inserting a new one?
Oh, I understand, you didn't point clearly that the tree changes after each query.
I pointed that in the first paragraph!