### pimenta's blog

By pimenta, 8 years ago,

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?

• 0

 » 8 years ago, # | ← Rev. 2 →   0 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.
•  » » 8 years ago, # ^ |   0 Sorry, I don't understand. It's for the whole test case??? It's like , but Q is not important? Is that it?
•  » » » 8 years ago, # ^ |   0 Oh, I get it. Each operation costs . It's actually for a test case. Thanks! Very helpful!
•  » » » 8 years ago, # ^ |   0 Yep, I'm sorry, fixed that.
•  » » » » 8 years ago, # ^ |   0 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!
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » » » 8 years ago, # ^ | ← Rev. 4 →   0 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?
•  » » » » » » » 4 years ago, # ^ |   -8 Could you please provide a link to the code for the same?
•  » » » » » » » » 4 years ago, # ^ |   0 OMG I can't remember the problem, sorry =(
 » 8 years ago, # |   0 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|).
•  » » 8 years ago, # ^ |   0 Indeed, trees have |E| = |V| - 1 = O(|V|)! But I was aware of that writing the post. I'll edit, thanks!
 » 8 years ago, # | ← Rev. 2 →   0 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!
•  » » 8 years ago, # ^ |   +10 And how do we update the LCA DS, removing an edge and inserting a new one?
•  » » » 8 years ago, # ^ |   0 Oh, I understand, you didn't point clearly that the tree changes after each query.
•  » » » » 8 years ago, # ^ |   0 I pointed that in the first paragraph!