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 v = root(u), cut(u), link(v, u), 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))