Блог пользователя pimenta

Автор pimenta, 9 лет назад, По-английски

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!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry, I don't understand. It's for the whole test case??? It's like , but Q is not important? Is that it?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oh, I get it. Each operation costs . It's actually for a test case. Thanks! Very helpful!

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yep, I'm sorry, fixed that.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 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!

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          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).

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
            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?

»
9 лет назад, # |
  Проголосовать: нравится 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|).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Indeed, trees have |E| = |V| - 1 = O(|V|)! But I was aware of that writing the post. I'll edit, thanks!

»
9 лет назад, # |
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!