Dynamic connectivity in forests with constant query time
An Euler tour tree is a linear representation of a tree. When the tour is stored in a balanced binary search tree keyed (implicitly) by the index in tour, the update and query operations can be done in $O(\log n)$. This is described in the referenced Erik's notes.

The tour can be stored in a two level array (similar to the structure described in section 2.2 of Data Structures for Traveling Salesmen). Each tree tour is stored in $O(\sqrt n)$ arrays with $O(\sqrt n)$ elements in each. Each tour element keeps a reference to its array, and each array keeps an reference to its parent array.

The update operations involves a constant number of arrays so it can be done in $O(\sqrt n)$. The query operation can be done in $O(1)$: The root of the tree containing each element is found and then compared. Each root is found in the position 0 of the first array of the tree tour. To find the tree tour containing a element just follows the element reference to its array and then follows the link to the parent array (that is, the tree tour).