TimonKnigge's blog

By TimonKnigge, history, 7 years ago, In English

Dear wise-and-all-knowing people of Codeforces, I have come to call on you for aid.

I'm trying to wrap my head around rerooting an Euler tour tree. In particular, I want to be able to still do link/cut operations. I can find some bits information about rerooting on the internet (which I understand), but I don't understand how I can continue using my Euler tour tree afterwards. Thus my question is: how, if possible at all, can I use Euler tour trees to support the operations cut(u), link(u, v) (assuming u has no parent), findroot(u) and makeroot(u), each in time? (or optionally with some extra -factors) In particular, makeroot(u) would preserve the general shape of the tree, i.e. you can't do attach(findroot(u), v)), instead all edges on the path from u to the root would be reversed.

Throughout this post let me use the left tree in this image as an example, with Euler tour 124252131. (these are the vertices in visited order, technically an Euler tour would yield the edges, but these two definitions are really equivalent, and I find this one easier to work with when doing link/cut operations)

Now, the problem comes from the fact that if you want to do e.g. a cut(u) operation, you need to cut out the segment from the first occurrence of u to its last occurrence. I.e. suppose we want to cut 2, then you get: 124252131  →  1 [24252] 131  →  24252   131 (removing a redundant 1 in front of the 2-subsequence). Note that we really need the first and last occurrence, the middle 2 is useless. If all you are doing is moving around complete segments, then the relative order of occurrences of the same vertex never changes, so you can just keep pointers to them for when you need them.

Then, rerooting. Since information about this is sparse on the internet, let me give a quick description. All that needs to be done is to rotate the sequence, with a small caveat wrt to the fact that the root of the tree appears one extra time at the end of the sequence. The algorithm is as follows:

  • remove the last occurrence of the old root from the sequence (at the end of the sequence, by definition)
  • rotate sequence so the first occurrence of the new root is at the front
  • append the new root to the end

So suppose we reroot the example tree at 5, then we get 124252131  →  12425213 (..1)  →  1242   5213  →  5213   1242 (5..)  →  521312425. Done. It seems a bit magical, but basically the idea behind this is that the sequence represents a cycle (namely, the Euler tour), and hence rotating the sequence just changes the starting vertex of the tour.

But then comes the problem. All the slides I found about this (e.g. here, slide 18) just call it quits at this point. But note that this rotation screwed up the first and last for some vertices (specifically, precisely for the vertices on the path from the new root to the old root, inclusive). In fact, any of the deg(u) or deg(u) + 1 occurrences of u might be the new first or last for a vertex. Since both the number of vertices on the path between the two roots, and the degrees of these vertices (~#occurrences) can potentially be linear in n, there is no way that we can quickly recompute first and last, i.e. we probably have to compute this information lazily. But I have no idea how to do this. And yet we really need these occurrences to quickly detach a subtree (or answer the query "is u an ancestor of v" or whatever).

Please send help.

(PS: I know I can use link/cut trees for this, but I'm explicitly asking about Euler tour trees. Not really for a problem (though you could test on e.g. SPOJ's DYNACON1), I'm just curious if this is possible (the fact that this rerooting is described in various lecture slides suggests to me that it is))

  • Vote: I like it
  • +65
  • Vote: I do not like it

»
7 years ago, # |
Rev. 5   Vote: I like it +39 Vote: I do not like it

Try storing directed edges in Euler tour instead of vertexes. E.g. instead of 1 2 4 2 5 2 1 3 1 you would store (1, 2); (2, 4); (4, 2); (2, 5); (5, 2); (2, 1); (1, 3); (3, 1) (any self-balanced tree would do, e.g. Cartesian/Treap or Splay). The nice thing of such representation is that invariants are very simple:

  • Each edge is stored exactly twice — once in each direction.
  • There are exactly 2(n - 1) elements of the tour.
  • You can cyclically shift the tour and it still remains tour, while in the node representation you'd get "border" node doubled.
  • In particular, first node of the first edge is the same as the second node of the last edge.

Modifications:

  • To cut an edge, you just find its two occurrences and remove them. Your tour is gracefully separated into two independent tours (ex.: prove it!).
  • To add an A → B edge, you should find arbitrary edge which ends in A and shift corresponding tour so that it's the last edge. Similarly, find arbitrary edge which starts in B and shift corresponding tour so that it's the first edge. Now, concatenate these tours while adding A → B in the middle and B → A in the end.

The only problem is with isolated nodes, but that can probably be solved by adding an imaginary edge from vertex to itself, which is never removed.

Anyway, all operations look like .

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your answer!

    I'll point out that I was actually trying to combine rerooting with a cut(u) operation (i.e. 'cut u from its parent') rather than a cut(u, v) operation, but I guess the former doesn't really make a lot of sense when combined with rerooting. (parents constantly changing and all that) I think it's just not possible at all.

    Adding self loops to vertices is also a nice idea, in fact I think it makes the 'add an edge (u, v)' operation much easier. After all, you say 'find an arbitrary edge ending in u'. You could manually keep a pointer to such an edge, but then you'd have to find a new one everytime such an edge is deleted. But when there are edges (u, u) in the tree you could always pick that edge to insert the new subtree after.

    Oh and self-loops also allow us to keep aggregate information for both edges and vertices in a subtree :-)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    How can we answer subtree queries using this representation?

    In the one mentioned in the blog we keep track of first & last occurrence of a node in the Euler Tour which makes finding the subtree of a particular node very convenient.

    Here I think we should instead keep track of the first edge where a node appears and the last edge where it appears also. But this way we're back with the same problem mentioned earlier.

    I think I'm missing something and any help would be greatly appreciated!

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      If you know parent of a vertex, you can cut the corresponding edge, query the whole tree, and then link the edge back.

      However, knowing the immediate parent (as opposed to known just the root) for each vertex is probably hard with pure Euler tour trees. I don't remember any good tricks for that right away.