+$AuvBvuC$ (with no~$u$ nor~$v$ in~$B$) splits to two sequences $AuC$ and $vBv$.
+If there was only a~single occurrence of~$v$, then $v$~was a~leaf and thus the sequence
+transforms from $AuvuC$ to $AuC$ and $v$~alone.
+
+\em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes its ET-sequence from $vAwBwCv$ to $wBwCvAw$.
+If $w$~was a~leaf, the sequence changes from $vAwCv$ to $wCvAw$. If $vw$ was the only edge of~$T$,
+the sequence $vw$ becomes $wv$. Note that this works regardless of the possible presence of~$w$ inside~$B$.
+
+\em{Joining} the roots of two trees by a~new edge makes their ET-sequences $vAv$ and~$wBw$
+combine to $vAvwBwv$. Again, we have to handle the cases when $v$ or~$w$ has degree~1 separately:
+$v$~and~$wBw$ combine to $vwBwv$, and $v$~with~$w$ makes $vwv$.
+
+\float{\valign{\vfil#\vfil\cr
+\hbox{\epsfbox{pic/ettree.eps}}\cr
+\noalign{\qquad\quad}
+ \halign{#\hfil\cr
+ $T_1: 0121034546474308980$,~~$T_2: aba$. \cr
+ $T_1-34: 01210308980, 4546474$. \cr
+ $T_1\hbox{~rooted at~3}: 3454647430898012103$. \cr
+ $T_1+0a+T_2$: $0121034546474308980aba0$. \cr
+ }\cr
+}}{Trees and their ET-sequences}
+
+If any of the occurrences that we have removed from the sequence was active, there is always
+a~new occurrence of the same vertex that can stand in its place and inherit the auxiliary data.
+
+The ET-trees will store the ET-sequences as $(a,b)$-trees with the parameter~$a$ set upon
+initialization of the structure and with $b=2a$. We know from the standard theorems of $(a,b)$-trees
+(see for example \cite{clrs}) that the depth of a~tree with $n$~leaves is always $\O(\log_a n)$
+and that all basic operations including insertion, deletion, search, splitting and joining the trees
+run in time $\O(b\log_a n)$ in the worst case.
+
+We will use the ET-trees to maintain a~spanning forest of the dynamic graph. The auxiliary data of
+each vertex will hold a~list of edges incident with the given vertex, that do not lie in the
+forest. Such edges are usually called the \df{non-tree edges.}
+
+\defn
+\df{Eulerian Tour trees (ET-trees)} are a~data structure that represents a~forest of trees and a~set of non-tree
+edges associated with the vertices of the forest. To avoid confusion, we will distinguish between
+\df{original} vertices and edges (of the given trees) and the vertices and edges of the
+data structure. The structure consists of:
+\itemize\ibull
+\:A~collection of $(a,b)$-trees of some fixed parameters $a$ and~$b$.
+ Each such tree corresponds to one of the original trees~$T$. Its
+ leaves (in the usual tree order) correspond to the elements
+ of an~ET-sequence for~$T$. Each two consecutive leaves $u$ and~$v$ are separated
+ by a~unique key stored in an~internal vertex of the $(a,b)$-tree. This key is used to represent
+ the original edge~$uv$. Each original edge is therefore kept in both its orientations.
+\:Mappings \<act>, \<edge> and \<twin>:
+ \itemize\icirc
+ \:$\<act>(v)$ maps each original vertex to the leaf containing its active occurrence;
+ \:$\<edge>(e)$ of an~original edge~$e$ is one of the internal keys representing~it;
+ \:$\<twin>(k)$ pairs an~internal key~$k$ with the other internal key of the same original edge.
+ \endlist
+\:A~list of non-tree edges placed in each leaf. The lists are allowed to be non-empty only
+ in the leaves that represent active occurrences of original vertices.
+\:Boolean \df{markers} in the internal vertices that signal presence of a~non-tree
+ edge anywhere in the subtree rooted at the internal vertex.
+\:Counters $\<leaves>(v)$ that contain the number of leaves in the subtree rooted at~$v$.
+\endlist
+
+\defn
+The ET-trees support the following operations on the original trees:
+\itemize\ibull
+\:\<Create> --- Create a~single-vertex tree.
+\:$\<Link>(u,v)$ --- Join two different trees by an~edge~$uv$ and return a~unique identifier
+ of this edge.
+\:$\<Cut>(e)$ --- Split a~tree by removing the edge~$e$ given by its identifier.
+\:$\<Connected>(u,v)$ --- Test if the vertices $u$ and~$v$ lie in the same tree.
+\:$\<Size>(v)$ --- Return the number of vertices in the tree containing the vertex~$v$.
+\:$\<InsertNontree>(v,e)$ --- Add a~non-tree edge~$e$ to the list at~$v$ and return a~unique
+ identifier of this edge.
+\:$\<DeleteNontree>(e)$ --- Delete a~non-tree edge~$e$ given by its identifier.
+\:$\<ScanNontree>(v)$ --- Return a~list of non-tree edges associated with the vertices
+ of the $v$'s tree.
+\endlist
+
+\impl
+We will implement the operations on the ET-trees by translating the intended changes of the
+ET-sequences to operations on the $(a,b)$-trees. The role of identifiers of the original vertices
+and edges will be of course played by pointers to the respective leaves and internal keys of
+the $(a,b)$-trees.
+
+\<Cut> of an~edge splits the $(a,b)$-tree at both internal keys representing the given edge
+and joins them back in the different order.
+
+\<Link> of two trees can be accomplished by making both vertices the roots of their trees first
+and joining the roots by an~edge afterwards. Re-rooting involves splits and joins of $(a,b)$-trees.
+As we can split at any occurrence of the new root vertex, we will use the active occurrence
+which we remember. Linking of the roots is translated to joining of the $(a,b)$-trees.
+
+\<Connected> follows parent pointers from both $u$ and~$v$ to the roots of their trees.
+Then it checks if the roots are equal.
+
+\<Size> finds the root and returns its counter.
+
+\<InsertNontree> finds the leaf $\<act>(v)$ containing the list of $v$'s non-tree edges
+and inserts the new edge there. The returned identifier will consist from the pointer to
+the edge and the vertex in whose list it is stored. Then we have to recalculate the markers
+on the path from $\<act>(v)$ to the root. \<DeleteNontree> is analogous.
+
+Whenever any other operation changes a~vertex of the tree, it will also update its marker and
+counter and, if necessary, the markers and counters on the path to the root.
+
+\<ScanNontree> traverses the tree recursively from the root, but it does not enter the
+subtrees whose roots are not marked.
+
+Analysis of time complexity of the operations is now straightforward:
+
+\thmn{Eulerian Tour trees, Henzinger and Rauch \cite{henzinger:randdyn}}\id{etthm}%
+The ET-trees perform the operations \<Link> and \<Cut> in time $\O(a\log_a n)$, \<Create>
+in $\O(1)$, \<Connected>, \<Size>, \<InsertNontree>, and \<DeleteNontree> in $\O(\log_a n)$, and
+\<ScanNontree> in $\O(a\log_a n)$ per edge reported. Here $n$~is the number of vertices
+in the original forest and $a\ge 2$ is an~arbitrary constant.
+
+\proof
+We set $b=2a$. Our implementation performs $\O(1)$ operations on the $(a,b)$-trees
+per operation on the ET-tree, plus $\O(1)$ other work. We apply the standard theorems
+on the complexity of $(a,b)$-trees \cite{clrs}.
+\qed
+
+\examplen{Connectivity acceleration}\id{accel}%
+In most cases, the ET-trees are used with $a$~constant, but sometimes choosing~$a$ as a~function
+of~$n$ can also have its beauty. Suppose that there is a~data structure which maintains an~arbitrary
+spanning forest of a~dynamic graph. Suppose also that the structure works in time $\O(\log^k n)$
+per operation and that it reports $\O(1)$ changes in the spanning forest for every change
+in the graph. If we keep the spanning forest in ET-trees with $a=\log n$, the updates of the
+data structure cost an~additional $\O(\log^2 n / \log\log n)$, but connectivity queries accelerate to $\O(\log
+n/\log\log n)$.
+
+\paran{ET-trees with weights}
+In some cases, we will also need a~representation of weighted graphs and enumerate the non-tree
+edges in order of their increasing weights (in fact, it will be sufficient to find the
+lightest one, remove it and iterate). This can be handled by a~minute modification of the
+ET-trees.
+
+The tree edges will remember their weight in the corresponding internal keys of the ET-tree.
+We replace each list of non-tree edges by an~$(a,b)$-tree keeping the edges sorted by weight.
+We also store the minimum element of that tree separately, so that it can be accessed in constant
+time. The boolean \em{marker} will then become the minimum weight of a~non-tree edge attached to the
+particular subtree, which can be recalculated as easy as the markers can. Searching for the
+lightest non-tree edge then just follows the modified markers.
+
+The time complexities of all operations therefore remain the same, with a~possible
+exception of the operations on non-tree edges, to which we have added the burden of
+updating the new $(a,b)$-trees. This however consists of $\O(1)$ updates per a~single
+call to \<InsertNontree> or \<DeleteNontree>, which takes $\O(a\log_a n)$ time only.
+We can therefore conclude:
+
+\corn{Weighted ET-trees}\id{wtet}%
+The time bounds in Theorem \ref{etthm} hold for the weighted ET-trees, too.
+
+
+%--------------------------------------------------------------------------------
+
+\section{Dynamic connectivity}
+
+The fully dynamic connectivity problem has a~long and rich history. In the 1980's, Frederickson \cite{frederickson:dynamic}
+has used his topological trees to construct a~dynamic connectivity algorithm of complexity $\O(\sqrt m)$ per update and
+$\O(1)$ per query. Eppstein et al.~\cite{eppstein:sparsify} have introduced a~sparsification technique which can bring the
+updates down to $\O(\sqrt n)$. Later, several different algorithms with complexity on the order of $n^\varepsilon$
+were presented by Henzinger and King \cite{henzinger:mst} and also by Mare\v{s} \cite{mares:dga}.
+A~polylogarithmic time bound was first reached by the randomized algorithm of Henzinger and King \cite{henzinger:randdyn}.
+The best result known as of now is the $\O(\log^2 n)$ time deterministic algorithm by Holm,
+de~Lichtenberg and Thorup \cite{holm:polylog}, which will we describe in this section.
+
+The algorithm will maintain a~spanning forest~$F$ of the current graph~$G$, represented by an~ET-tree
+which will be used to answer connectivity queries. The edges of~$G\setminus F$ will be stored as~non-tree
+edges in the ET-tree. Hence, an~insertion of an~edge to~$G$ either adds it to~$F$ or inserts it as non-tree.
+Deletions of non-tree edges are also easy, but when a~tree edge is deleted, we have to search for its
+replacement among the non-tree edges.
+
+To govern the search in an~efficient way, we will associate each edge~$e$ with a~level $\ell(e) \le
+L = \lfloor\log_2 n\rfloor$. For each level~$i$, we will use~$F_i$ to denote the subforest
+of~$F$ containing edges of level at least~$i$. Therefore $F=F_0 \supseteq F_1 \supseteq \ldots \supseteq F_L$.
+We will maintain the following \em{invariants:}
+
+{\narrower
+\def\iinv{{\bo I\the\itemcount~}}
+\numlist\iinv
+\:$F$~is the maximum spanning forest of~$G$ with respect to the levels. (In other words,
+if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$.)
+\:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices each.
+(This implies that it does not make sense to define~$F_i$ for $i>L$, because it would be empty
+anyway.)
+\endlist
+}
+
+At the beginning, the graph contains no edges, so both invariants are trivially
+satisfied. Newly inserted edges can enter level~0, which cannot break I1 nor~I2.
+
+When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
+trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
+smaller one. We will try to find the replacement edge of the highest possible
+level that connects the spanning tree back. From I1, we know that such an~edge cannot belong to
+a~level greater than~$\ell$, so we start looking for it at level~$\ell$. According
+to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has
+at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can increase the levels
+of all edges of~$T_1$ without violating either invariant.
+
+We now start enumerating the non-tree edges incident with~$T_1$. Each such edge
+is either local to~$T_1$ or it joins $T_1$ with~$T_2$. We will therefore check each edge
+whether its other endpoint lies in~$T_2$ and if it does, we have found the replacement
+edge, so we insert it to~$F_\ell$ and stop. Otherwise we move the edge one level up. (This
+will be the grist for the mill of our amortization argument: We can charge most of the work at level
+increases and we know that the level of each edge can reach at most~$L$.)
+
+If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next
+lower level and so on. If there is no replacement edge at level~0, the tree~$T$
+remains disconnected.
+
+\impl
+For each level, we will use a~separate ET-tree ${\cal E}_\ell$ with~$a$ set to~2,
+which will represent the forest~$F_i$ and the non-tree edges at that particular level.
+Besides operations on the non-tree edges, we also need to find the tree edges of level~$\ell$
+when we want to bring them one level up. This can be accomplished either by modifying the ET-trees
+to attach two lists of edges attached to vertices instead of one, or by using a~second ET-tree.
+
+\algn{Insertion of an~edge}
+\algo
+\algin An~edge $uv$ to insert.
+\:$\ell(uv) \= 0$.
+\:Ask the ET-tree ${\cal E}_0$ if $u$ and~$v$ are in the same component. If they are:
+\::Add $uv$ to the list of non-tree edges in ${\cal E}_0$ at both $u$ and~$v$.
+\:Otherwise:
+\::Add $uv$ to~$F_0$.
+\endalgo
+
+\algn{Deletion of an~edge}
+\algo
+\algin An~edge $uv$ to delete.
+\:$\ell \= \ell(uv)$.
+\:If $uv$ is a~non-tree edge:
+\::Remove $uv$ from the lists of non-tree edges at both $u$ and~$v$ in~${\cal E}_{\ell}$.
+\:Otherwise:
+\::Remove $uv$ from~$F_\ell$ and hence also from $F_0,\ldots,F_{\ell-1}$.
+\::Call $\<Replace>(uv,\ell)$ to get the replacement edge~$f$.
+\::Insert $f$ to~$F_0,\ldots,F_{\ell(f)}$.
+\endalgo
+
+\algn{$\<Replace>(uv,i)$ -- Search for replacement for edge~$uv$ at level~$i$}
+\algo
+\algin An~edge~$uv$ to replace and a~level~$i$ such that there is no replacement
+at levels greater than~$i$.
+\:Let $T_1$ and~$T_2$ be the trees in~$F_i$ containing $u$ and~$v$ respectively.
+\:If $n(T_1) > n(T_2)$, swap $T_1$ with~$T_2$.
+\:Find all level~$i$ edges in~$T_1$ using ${\cal E}_i$ and move them to level~$i+1$.
+\:Enumerate non-tree edges incident with vertices of~$T_1$ and stored in ${\cal E}_i$.
+ For each edge~$xy$, $x\in T_1$, do:
+\::If $y\in T_2$, remove~$xy$ from~${\cal E}_i$ and return it to the caller.
+\::Otherwise increase $\ell(xy)$ by one.
+ \hfil\break
+ This includes deleting~$xy$ from~${\cal E}_i$ and inserting it to~${\cal E}_{i+1}$.
+\:If $i>0$, call $\<Replace>(xy,i-1)$.
+\:Otherwise return \<null>.
+\algout The replacement edge.
+\endalgo