🗂️Data StructureAdvanced

Euler Tour Tree

Key Points

  • •
    An Euler Tour Tree represents each rooted tree as a DFS open/close sequence so that every subtree is a single contiguous interval.
  • •
    By storing the Euler tour in a balanced binary search tree (e.g., treap or splay) keyed by position, we can split and merge the tour in O(log n) time.
  • •
    This makes dynamic operations like reroot, link (attach a tree as a child), cut (detach a subtree), and subtree aggregation queries efficient.
  • •
    To count only each vertex once, store the vertex weight on the entry occurrence and zero on the exit occurrence; the subtree sum is then a range sum over [in[v], out[v]].
  • •
    Euler Tour Trees are excellent for subtree queries and dynamic connectivity in forests but do not directly support path queries between two arbitrary nodes.
  • •
    Compared to Link-Cut Trees, Euler Tour Trees are simpler to implement for subtree operations but less flexible for path aggregates.
  • •
    Expected time per operation is O(log n) with treaps since the tree height is logarithmic in expectation.
  • •
    Total space is O(n) nodes, but in practice you store 2 occurrences per vertex (enter and exit), so the implicit sequence length is 2n.

Prerequisites

  • →Depth-First Search (DFS) — Euler tours are built from DFS entry and exit events.
  • →Balanced Binary Search Trees — ETT stores the tour in a balanced BST to support split/merge in O(log n).
  • →Treaps or Splay Trees — An implicit treap/splay is the core engine for ETT; understanding rotations and expected height is necessary.
  • →Range Query Data Structures — Fenwick/segment trees help understand how subtree queries become range queries.
  • →Amortized/Expected Complexity — ETT performance relies on expected O(log n) time bounds.
  • →Tree Terminology (root, subtree, parent/child) — Correctly interpreting [in[v], out[v]] intervals requires rooted tree semantics.

Detailed Explanation

Tap terms for definitions

01Overview

An Euler Tour Tree (ETT) is a dynamic data structure for maintaining a forest (a collection of trees) under edge insertions and deletions while supporting efficient subtree queries. It encodes each rooted tree as the sequence of a depth-first search (DFS) "enter" and "exit" events: when we first enter a node, we push an entry marker; when we finish exploring its subtree, we push an exit marker. In this sequence, every subtree forms one contiguous block. If we store this sequence inside a balanced binary search tree (like a treap or splay) keyed by implicit position, we can split and merge the sequence in O(log n) time, which corresponds to changing the underlying tree structure.

The power of ETT comes from two facts: (1) subtree = contiguous range in the Euler tour; (2) balanced BSTs support range operations efficiently. For example, to answer "what is the sum of weights in v's subtree?", assign v's weight to v's entry marker and zero to its exit marker. The sum over [in[v], out[v]] in the Euler tour then gives the subtree sum. To attach a whole tree as a child, we insert one tour into the other's range before the parent's exit marker; to detach a subtree, we cut out its contiguous block.

ETTs are easier than Link-Cut Trees when you only need subtree operations. However, they do not directly support path queries between arbitrary nodes; for that, you would typically consider Link-Cut Trees or Heavy-Light Decomposition (HLD).

02Intuition & Analogies

Imagine walking through a museum where each room is a node, and every time you step into a room you stamp an "ENTER(room)" in your notebook and every time you leave you stamp an "EXIT(room)". Your notebook ends up with a sequence like ENTER(A), ENTER(B), EXIT(B), ENTER(C), EXIT(C), EXIT(A). Notice that everything about room B (its whole subtree) is between ENTER(B) and EXIT(B) — a single continuous stretch in the notebook.

Now think of the notebook pages as arranged on a long tape. If you cut out the strip between ENTER(X) and EXIT(X) and set it aside, you literally separated X's whole subtree. To make X a child of Y, you can glue X's strip just before EXIT(Y) — now, when you read the tape, X is clearly inside Y's subtree. To make X the root of the whole tour, you rotate the tape so ENTER(X) comes first and EXIT(X) comes last. All these are cut-and-paste operations.

Computers are good at cut-and-paste in logarithmic time if the tape is stored in a balanced binary tree that supports split and merge by position (an implicit treap or splay). Each node in that balanced BST represents a token on the tape (an ENTER or EXIT), and the tree maintains extra info like the sum of values in its subtree. When you need a subtree sum for X, you split the tape to isolate ENTER(X)..EXIT(X), read the sum from the augmented node, and glue everything back together. That's the entire idea of Euler Tour Trees: convert subtree questions into range questions on a sequence, and use a data structure that’s great at handling ranges.

03Formal Definition

Let T = (V, E) be a rooted tree. The Euler tour of T is the sequence obtained by a DFS that records an entry token (v) when visiting v and an exit token (v) after processing v's children. This creates a sequence S of length 2. The subtree of v corresponds to the contiguous subsequence from (v) (inclusive) to (v) (inclusive). Define a weight function w: and extend it to tokens by assigning w((v)) = w(v) and w((v)) = 0. Then the sum over the subtree of v equals the sum of w over the interval [(v), (v)] in S. An Euler Tour Tree maintains, for each tree in a dynamic forest, an implicit sequence S inside a balanced binary search tree B (e.g., treap or splay) keyed by position. B supports split(B, k) to separate the first k tokens and merge(B1, B2) to concatenate sequences, both in O(log n). Dynamic operations are realized as follows: reroot(r) cyclically shifts S so that (r) is the first token and (r) the last; link(u, v) (making v a child of u) inserts the entire sequence for v just before (u); cut(u, v) removes the contiguous block for v's subtree (after rerooting at u if necessary). Connectivity queries reduce to checking if (u) and (v) belong to the same balanced BST. Time bounds are O(log n) expected per operation with treaps due to their expected height, and space is O() tokens, which is 2 per vertex in the entry/exit representation.

04When to Use

Use Euler Tour Trees when you maintain a dynamic forest and your queries revolve around subtrees with respect to a chosen root: subtree sums, subtree minimum/maximum, subtree size, or adding/removing whole subtrees by link/cut. ETT shines in scenarios like maintaining dynamic group hierarchies, folder trees, organizational charts, or game trees where attaching/detaching entire branches is frequent and you need quick subtree aggregates or updates.

Competitive programming tasks often require dynamic connectivity in forests, with operations like link(u, v), cut(u, v), add value to node, and query sum in subtree(v). ETTs handle these cleanly, typically with fewer edge cases than Link-Cut Trees when the aggregation is on subtrees rather than paths. If you need to frequently reroot to interpret queries relative to a different root, ETT supports reroot in O(log n) via a rotation of the sequence.

Do not use ETT when the primary operation is aggregating along arbitrary u–v paths (path sums, path minima). While you can sometimes emulate specific path operations with reroot and subtree tricks, ETT is not the right tool for general path queries; prefer Link-Cut Trees or Heavy-Light Decomposition in such cases. Also, if your tree is static (no edge updates), a simple Euler tour array plus a Fenwick/segment tree is both faster and easier to implement.

⚠️Common Mistakes

• Confusing subtree vs path: ETTs make subtree queries trivial but do not directly support path queries. If you try to answer u–v path aggregates by naive subtree operations, the results will be wrong unless you apply nontrivial transformations.

• Forgetting the entry/exit trick: If you put the vertex weight on both entry and exit tokens, you will double-count. Standard practice is to store w(v) on e_{in}(v) and 0 on e_{out}(v), so the range sum equals the subtree sum without corrections.

• Not maintaining the rooted invariant: Subtree(v) corresponds to [e_{in}(v), e_{out}(v)] for the current root. If you want a specific root semantics, call reroot(r) first. Link and cut should be implemented relative to a consistent root (e.g., making one endpoint the parent).

• Mishandling split/merge boundaries: Off-by-one errors when splitting at indices of e_{in}(v) and e_{out}(v) are common. Carefully define whether your split takes the first k elements and verify that [in, out] is inclusive.

• Ignoring connectivity checks: Linking nodes already in the same tree creates cycles and breaks the Euler tour invariant. Always check connectivity before link, and ensure cut(u, v) actually targets an existing parent–child relation (after reroot(u), v must lie in a proper subtree).

• Missing parent pointers or failing to update them: If you compute a node’s index by walking parent pointers, ensure all merge/split operations maintain correct parent fields; otherwise indices become wrong and the structure corrupts.

Key Formulas

Balanced BST Operation Time

Explanation: Split and merge on an implicit treap (or splay) are logarithmic in the number of nodes. This underpins all ETT operations like reroot, link, cut, and range queries.

Euler Tour Length

Explanation: In the entry/exit representation, each vertex contributes exactly two tokens, so the total sequence length for a tree with |V| vertices is 2|V|.

Weight Transfer to Tokens

Explanation: If weights are on entry tokens and zero on exit tokens, the sum over vertices equals the sum over tokens in the Euler tour sequence, preserving aggregates.

Subtree Sum by Interval

Explanation: The subtree of v is a contiguous interval in the sequence from in[v] to out[v], so summing weights over that range yields the subtree sum.

Treap Height

Explanation: The expected height of a treap is logarithmic, so all structural operations used by ETT are logarithmic in expectation.

Space Usage

Explanation: ETT stores a constant number of tokens per vertex (two in the entry/exit model), plus balanced BST overhead, for overall linear space.

Bracket Invariant

Explanation: For a well-formed Euler tour under a chosen root, each vertex’s entry index precedes its exit index, ensuring valid contiguous blocks for subtrees.

Complexity Analysis

Let n be the number of vertices. In the entry/exit representation, the Euler tour sequence has exactly 2n tokens. We store this sequence in an implicit balanced BST (treap in our code). Every structural operation — split at a position k and merge two sequences — takes O(log n) expected time, because the expected height of a treap is O(log n). Therefore: • reroot(v): implemented by at most three splits and two merges, is O(log n) expected. • link(u, v): two reroots plus a constant number of split/merge operations, overall O(log n) expected, provided u and v are in different trees. • cut(u, v): one reroot and two splits plus one merge, overall O(log n) expected. • subtree query (e.g., sum): two splits to isolate [in[v], out[v]] and two merges to restore, O(log n) expected. With augmentation (sum in each node), the range sum is O(1) after splitting. • connectivity(u, v): O(h) to climb parent pointers to find roots, where h = O(log n) expected; thus O(log n) expected. Space usage is linear in the number of tokens (2n) plus node overhead, giving O(n). If you extend the structure with lazy propagation for subtree updates, each node additionally stores lazy tags; this does not change the asymptotic complexity. Constants are small in a treap; splay trees offer similar guarantees but with amortized bounds and potentially larger constant factors due to rotations. In practice, ETT is fast enough for 2200–2600 CF tasks involving dynamic forests with subtree queries.

Code Examples

Static Euler Tour + Fenwick Tree for Subtree Sum Queries
1#include <bits/stdc++.h>
2using namespace std;
3
4// Static tree: Euler tour array + Fenwick (BIT) for subtree sums.
5// Vertex weights are counted once using entry time only.
6
7struct Fenwick {
8    int n; vector<long long> bit;
9    Fenwick(int n=0): n(n), bit(n+1, 0) {}
10    void add(int i, long long delta){ // 1-based index
11        for(; i<=n; i+=i&-i) bit[i]+=delta;
12    }
13    long long sumPrefix(int i){ long long s=0; for(; i>0; i-=i&-i) s+=bit[i]; return s; }
14    long long sumRange(int l, int r){ if(r<l) return 0; return sumPrefix(r)-sumPrefix(l-1); }
15};
16
17int n; 
18vector<vector<int>> g;
19vector<int> tin, tout, euler; // euler stores entry order
20int timer_ = 0;
21
22void dfs(int u, int p){
23    tin[u] = ++timer_;
24    for(int v: g[u]) if(v!=p) dfs(v, u);
25    tout[u] = timer_; // inclusive interval [tin[u], tout[u]]
26}
27
28int main(){
29    ios::sync_with_stdio(false);
30    cin.tie(nullptr);
31
32    // Example:
33    // n=5, edges: 1-2, 1-3, 3-4, 3-5
34    // weights: w1..w5
35    cin >> n;
36    g.assign(n+1, {});
37    for(int i=0;i<n-1;i++){
38        int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u);
39    }
40    vector<long long> w(n+1);
41    for(int i=1;i<=n;i++) cin>>w[i];
42
43    tin.assign(n+1,0); tout.assign(n+1,0); timer_=0;
44    dfs(1, 0); // choose root=1
45
46    Fenwick ft(n);
47    // Put weight at entry only
48    for(int v=1; v<=n; v++) ft.add(tin[v], w[v]);
49
50    int q; cin>>q;
51    // Supported queries:
52    // 1 v -> print sum of subtree(v)
53    // 2 v x -> set weight[v]=x
54    while(q--){
55        int type; cin>>type;
56        if(type==1){
57            int v; cin>>v;
58            long long ans = ft.sumRange(tin[v], tout[v]);
59            cout << ans << '\n';
60        } else if(type==2){
61            int v; long long x; cin>>v>>x;
62            long long delta = x - w[v];
63            w[v] = x;
64            ft.add(tin[v], delta);
65        }
66    }
67    return 0;
68}
69

This program demonstrates the static version: compute an Euler tour of a rooted tree, assign each vertex’s weight to its entry time, and use a Fenwick tree over the entry order. Subtree(v) is the index interval [tin[v], tout[v]]; querying this range returns the sum of weights in v’s subtree. Point updates are supported by adding the delta at tin[v].

Time: O((n+q) log n)Space: O(n)
Dynamic Euler Tour Tree with Implicit Treap: reroot, link, cut, subtree sum, connectivity
1#include <bits/stdc++.h>
2using namespace std;
3
4// Euler Tour Tree using implicit treap (expected O(log n)).
5// Each vertex v has two treap nodes: in[v] carries weight w[v], out[v] carries 0.
6// Subtree(v) corresponds to the contiguous interval [in[v], out[v]].
7// Operations provided:
8// - make_root(v)
9// - connected(u, v)
10// - link(u, v): make v a child of u (forests only; must be in different trees)
11// - cut(u, v): remove the edge between u (as ancestor) and v (its subtree) by reroot(u) then detaching [in[v], out[v]]
12// - set_value(v, x): update the weight of vertex v
13// - subtree_sum(v): sum of weights in subtree of v under current root
14// Note: This structure is for subtree operations; path queries are not directly supported.
15
16struct Node {
17    // implicit treap node representing an ENTER or EXIT token
18    int prior;               // heap priority
19    int sz;                  // subtree size (number of tokens)
20    long long val;           // value on this token (w(v) for ENTER, 0 for EXIT)
21    long long sum;           // sum of val over subtree
22    bool is_entry;           // true for ENTER(v), false for EXIT(v)
23    int vid;                 // vertex id this token belongs to (for debug)
24    Node *l, *r, *p;
25    Node(int prior, long long val, bool is_entry, int vid):
26        prior(prior), sz(1), val(val), sum(val), is_entry(is_entry), vid(vid), l(nullptr), r(nullptr), p(nullptr) {}
27};
28
29mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
30
31int getsz(Node* t){ return t ? t->sz : 0; }
32long long getsum(Node* t){ return t ? t->sum : 0; }
33
34void pull(Node* t){
35    if(!t) return;
36    t->sz = 1 + getsz(t->l) + getsz(t->r);
37    t->sum = t->val + getsum(t->l) + getsum(t->r);
38    if(t->l) t->l->p = t;
39    if(t->r) t->r->p = t;
40}
41
42// Split by first k tokens: [0..k-1] goes to a, [k..end] to b
43void split(Node* t, int k, Node*& a, Node*& b){
44    if(!t){ a=b=nullptr; return; }
45    if(getsz(t->l) >= k){
46        split(t->l, k, a, t->l);
47        b = t;
48        pull(b);
49        if(a) a->p = nullptr;
50        if(b) b->p = nullptr;
51    } else {
52        split(t->r, k - getsz(t->l) - 1, t->r, b);
53        a = t;
54        pull(a);
55        if(a) a->p = nullptr;
56        if(b) b->p = nullptr;
57    }
58}
59
60Node* merge(Node* a, Node* b){
61    if(!a) { if(b) b->p=nullptr; return b; }
62    if(!b) { if(a) a->p=nullptr; return a; }
63    if(a->prior > b->prior){
64        a->r = merge(a->r, b);
65        pull(a);
66        a->p = nullptr;
67        return a;
68    } else {
69        b->l = merge(a, b->l);
70        pull(b);
71        b->p = nullptr;
72        return b;
73    }
74}
75
76Node* getRoot(Node* x){
77    while(x && x->p) x = x->p;
78    return x;
79}
80
81int getIndex(Node* x){
82    // 0-based position of x in its treap (in-order)
83    int idx = getsz(x->l);
84    while(x->p){
85        if(x == x->p->r){
86            idx += 1 + getsz(x->p->l);
87        }
88        x = x->p;
89    }
90    return idx;
91}
92
93struct EulerTourTree {
94    int n;
95    vector<Node*> inTok, outTok;
96    vector<long long> w;
97
98    EulerTourTree(int n=0): n(n), inTok(n+1,nullptr), outTok(n+1,nullptr), w(n+1,0) {
99        // initialize each vertex as its own tree: [in(v), out(v)]
100        for(int v=1; v<=n; v++){
101            int p1 = (int)rng();
102            int p2 = (int)rng();
103            inTok[v]  = new Node(p1, 0, true, v);
104            outTok[v] = new Node(p2, 0, false, v);
105            // set initial sequence in[v], out[v]
106            Node* t = merge(inTok[v], outTok[v]);
107            (void)t; // root is reachable via any token's getRoot later
108        }
109    }
110
111    void set_value(int v, long long nv){
112        long long delta = nv - w[v];
113        w[v] = nv;
114        // Apply delta to entry token only
115        Node* x = inTok[v];
116        x->val += delta;
117        // update sums up to root
118        while(x){ pull(x); x = x->p; }
119    }
120
121    bool connected(int u, int v){
122        if(u==v) return true;
123        return getRoot(inTok[u]) == getRoot(inTok[v]);
124    }
125
126    // Place ENTER(v) at beginning and EXIT(v) at the end of its tree's sequence
127    void make_root(int v){
128        Node* r = getRoot(inTok[v]);
129        if(!r) return;
130        int i = getIndex(inTok[v]);
131        int j = getIndex(outTok[v]);
132        if(i > j) swap(i, j); // robust to accidental disorder
133        Node *A, *B, *C;
134        // split at j+1: [0..j] and [j+1..end]
135        split(r, j+1, A, C);
136        // split A at i: [0..i-1], [i..j]
137        Node *L, *M;
138        split(A, i, L, M);
139        // desired order: M + C + L
140        Node* tmp = merge(M, C);
141        Node* nr = merge(tmp, L);
142        (void)nr; // structure updated; tokens know their root via parent pointers
143    }
144
145    // Insert tree of v as the last child inside u's subtree: before EXIT(u)
146    void link(int u, int v){
147        // preconditions: u and v are in different trees
148        if(connected(u, v)) return; // or throw
149        make_root(u);
150        make_root(v);
151        Node* ru = getRoot(inTok[u]);
152        // after make_root(u): EXIT(u) should be last; split off the last token
153        int su = getsz(ru);
154        Node *A, *last;
155        split(ru, su-1, A, last); // last is EXIT(u)
156        Node* rv = getRoot(inTok[v]);
157        Node* merged = merge(A, rv);
158        Node* nr = merge(merged, last);
159        (void)nr;
160    }
161
162    // Cut the edge between u (ancestor) and v by isolating v's subtree.
163    // Implementation: reroot at u, then remove [in[v], out[v]] block.
164    void cut(int u, int v){
165        if(!connected(u, v)) return; // or throw
166        make_root(u);
167        Node* r = getRoot(inTok[u]);
168        int i = getIndex(inTok[v]);
169        int j = getIndex(outTok[v]);
170        if(i > j) swap(i, j);
171        Node *A, *BC; split(r, j+1, A, BC); // [0..j], [j+1..]
172        Node *B, *C; split(A, i, B, C);     // [0..i-1], [i..j]
173        // B + BC is the remaining tree; C is the detached subtree tour
174        Node* rem = merge(B, BC);
175        (void)rem; // structures updated
176    }
177
178    long long subtree_sum(int v){
179        Node* r = getRoot(inTok[v]);
180        int i = getIndex(inTok[v]);
181        int j = getIndex(outTok[v]);
182        if(i > j) swap(i, j);
183        Node *A, *BC; split(r, j+1, A, BC);
184        Node *B, *C; split(A, i, B, C);
185        long long ans = getsum(C);
186        // merge back to restore structure
187        Node* left = merge(B, C);
188        Node* nr = merge(left, BC);
189        (void)nr;
190        return ans;
191    }
192};
193
194int main(){
195    ios::sync_with_stdio(false);
196    cin.tie(nullptr);
197
198    int n, q; // dynamic forest with n vertices, q operations
199    cin >> n >> q;
200    EulerTourTree ett(n);
201    for(int v=1; v<=n; v++){
202        long long w; cin >> w; ett.set_value(v, w);
203    }
204
205    // Supported ops:
206    // link u v      -> attach v as a child of u (must be in different trees)
207    // cut u v       -> remove edge between u (ancestor after reroot) and v (its subtree)
208    // reroot v      -> make v the root of its tree
209    // sum v         -> subtree sum of v
210    // set v x       -> set node v's weight to x
211    // conn u v      -> print 1 if connected else 0
212
213    while(q--){
214        string op; cin >> op;
215        if(op=="link"){
216            int u, v; cin >> u >> v; ett.link(u, v);
217        } else if(op=="cut"){
218            int u, v; cin >> u >> v; ett.cut(u, v);
219        } else if(op=="reroot"){
220            int v; cin >> v; ett.make_root(v);
221        } else if(op=="sum"){
222            int v; cin >> v; cout << ett.subtree_sum(v) << '\n';
223        } else if(op=="set"){
224            int v; long long x; cin >> v >> x; ett.set_value(v, x);
225        } else if(op=="conn"){
226            int u, v; cin >> u >> v; cout << (ett.connected(u, v) ? 1 : 0) << '\n';
227        }
228    }
229    return 0;
230}
231

This is a full Euler Tour Tree using an implicit treap. Each vertex v has two tokens: ENTER(v) carries w(v) and EXIT(v) carries 0. The subtree of v is the interval [ENTER(v), EXIT(v)]. Reroot rotates the sequence to start at ENTER(v) and end at EXIT(v). Linking inserts one tour before EXIT(u), making v a child of u. Cutting removes the contiguous block of a subtree after reroot(u). Subtree sums and connectivity are supported in O(log n) expected time.

Time: O(log n) expected per operationSpace: O(n)
Minimal Dynamic Connectivity with Euler Tour Tree (no weights)
1#include <bits/stdc++.h>
2using namespace std;
3
4// A lighter ETT variant for connectivity only. Each vertex v has ENTER and EXIT tokens with value omitted.
5// Supports: connected, reroot, link, cut. No sums stored.
6
7struct Node {
8    int prior, sz; bool is_entry; int vid; Node *l,*r,*p;
9    Node(int pr, bool en, int v): prior(pr), sz(1), is_entry(en), vid(v), l(nullptr), r(nullptr), p(nullptr) {}
10};
11
12mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
13int getsz(Node* t){ return t? t->sz:0; }
14void pull(Node* t){ if(!t) return; t->sz = 1 + getsz(t->l) + getsz(t->r); if(t->l) t->l->p=t; if(t->r) t->r->p=t; }
15
16void split(Node* t, int k, Node*& a, Node*& b){
17    if(!t){ a=b=nullptr; return; }
18    if(getsz(t->l) >= k){ split(t->l, k, a, t->l); b=t; pull(b); if(a) a->p=nullptr; if(b) b->p=nullptr; }
19    else { split(t->r, k - getsz(t->l) - 1, t->r, b); a=t; pull(a); if(a) a->p=nullptr; if(b) b->p=nullptr; }
20}
21Node* merge(Node* a, Node* b){ if(!a){ if(b) b->p=nullptr; return b;} if(!b){ if(a) a->p=nullptr; return a;} if(a->prior > b->prior){ a->r=merge(a->r,b); pull(a); a->p=nullptr; return a;} else { b->l=merge(a,b->l); pull(b); b->p=nullptr; return b; } }
22Node* root(Node* x){ while(x&&x->p) x=x->p; return x; }
23int indexOf(Node* x){ int i=getsz(x->l); while(x->p){ if(x==x->p->r) i+=1+getsz(x->p->l); x=x->p; } return i; }
24
25struct ETTConn {
26    int n; vector<Node*> inTok, outTok;
27    ETTConn(int n=0): n(n), inTok(n+1,nullptr), outTok(n+1,nullptr) {
28        for(int v=1; v<=n; v++){
29            inTok[v] = new Node((int)rng(), true, v);
30            outTok[v]= new Node((int)rng(), false, v);
31            Node* t = merge(inTok[v], outTok[v]); (void)t;
32        }
33    }
34    bool connected(int u,int v){ return root(inTok[u])==root(inTok[v]); }
35    void make_root(int v){ Node* r = root(inTok[v]); int i=indexOf(inTok[v]); int j=indexOf(outTok[v]); if(i>j) swap(i,j); Node *A,*C,*L,*M; split(r,j+1,A,C); split(A,i,L,M); Node* nr = merge(merge(M,C),L); (void)nr; }
36    void link(int u,int v){ if(connected(u,v)) return; make_root(u); make_root(v); Node* ru=root(inTok[u]); Node* rv=root(inTok[v]); int su=getsz(ru); Node *A,*last; split(ru,su-1,A,last); Node* nr=merge(merge(A,rv),last); (void)nr; }
37    void cut(int u,int v){ if(!connected(u,v)) return; make_root(u); Node* r=root(inTok[u]); int i=indexOf(inTok[v]); int j=indexOf(outTok[v]); if(i>j) swap(i,j); Node *A,*BC,*B,*C; split(r,j+1,A,BC); split(A,i,B,C); Node* rem = merge(B,BC); (void)rem; }
38};
39
40int main(){
41    ios::sync_with_stdio(false); cin.tie(nullptr);
42    int n,q; cin>>n>>q; ETTConn ett(n);
43    while(q--){
44        string op; cin>>op;
45        if(op=="link"){ int u,v; cin>>u>>v; ett.link(u,v); }
46        else if(op=="cut"){ int u,v; cin>>u>>v; ett.cut(u,v); }
47        else if(op=="conn"){ int u,v; cin>>u>>v; cout<<(ett.connected(u,v)?1:0)<<'\n'; }
48        else if(op=="reroot"){ int v; cin>>v; ett.make_root(v); }
49    }
50    return 0;
51}
52

A minimal Euler Tour Tree tailored to dynamic connectivity. It omits weights and sums, keeping only the structural operations. It is useful to validate and unit-test link/cut/reroot logic before adding augmentations.

Time: O(log n) expected per operationSpace: O(n)