Keep the Euler tour of every tree of a forest in a balanced sequence (a treap with parent pointers). Then link, cut and reroot are a constant number of splits and merges, connectivity is “same treap root”, and subtree / component aggregates are range aggregates over a contiguous block of the tour, all expected. Path aggregates are not supported (use a Link-Cut Tree). This is the structure inside Holm–de Lichtenberg–Thorup dynamic connectivity.
Tour representation: one node per vertex and one per directed edge. The tour of a tree rooted at is , then for each child : arc , the tour of , arc . Rerooting is a cyclic rotation; the subtree of below edge – is the block strictly between arcs and when the tour starts at .
struct EulerTourTree { // vertices 0..n-1, vertex values, forest under link/cut
struct Node { int l = 0, r = 0, p = 0, sz = 1, cnt = 0; ull pri = 0; ll val = 0, sum = 0; };
int n; vector<Node> t; map<pair<int, int>, int> arc; vector<int> freeIds; mt19937_64 rng{987654321};
EulerTourTree(int n) : n(n), t(n + 1) { t[0].sz = 0; for (int v = 1; v <= n; v++) t[v].cnt = 1, t[v].pri = rng(); }
void pull(int x) {
auto &a = t[t[x].l], &b = t[t[x].r];
t[x].sz = a.sz + b.sz + 1; t[x].cnt = a.cnt + b.cnt + (x <= n); t[x].sum = a.sum + b.sum + (x <= n ? t[x].val : 0);
if (t[x].l) t[t[x].l].p = x;
if (t[x].r) t[t[x].r].p = x;
}
int merge(int a, int b) {
if (!a || !b) { int r = a | b; if (r) t[r].p = 0; return r; }
if (t[a].pri > t[b].pri) { t[a].r = merge(t[a].r, b); pull(a); t[a].p = 0; return a; }
t[b].l = merge(a, t[b].l); pull(b); t[b].p = 0; return b;
}
void split(int x, int k, int& a, int& b) { // first k nodes go to a
if (!x) { a = b = 0; return; }
if (t[t[x].l].sz >= k) { split(t[x].l, k, a, t[x].l); pull(x); b = x; }
else { split(t[x].r, k - t[t[x].l].sz - 1, t[x].r, b); pull(x); a = x; }
if (a) t[a].p = 0;
if (b) t[b].p = 0;
}
int root(int x) const { while (t[x].p) x = t[x].p; return x; }
int index(int x) const {
int i = t[t[x].l].sz;
for (; t[x].p; x = t[x].p) if (t[t[x].p].r == x) i += t[t[t[x].p].l].sz + 1;
return i;
}
int newArc(int u, int v) {
int x; if (sz(freeIds)) x = freeIds.back(), freeIds.pop_back(); else x = sz(t), t.emplace_back();
t[x] = Node(); t[x].pri = rng(); arc[{u, v}] = x; return x;
}
int reroot(int v) { // node ids are vertex + 1; returns the new treap root
int x = v + 1, r = root(x), i = index(x), a, b; split(r, i, a, b); return merge(b, a);
}
bool connected(int u, int v) const { return root(u + 1) == root(v + 1); }
bool link(int u, int v) {
if (connected(u, v)) return false;
int A = reroot(u), B = reroot(v), e1 = newArc(u, v), e2 = newArc(v, u);
merge(merge(merge(A, e1), B), e2); return true;
}
bool cut(int u, int v) {
auto it1 = arc.find({u, v}), it2 = arc.find({v, u}); if (it1 == arc.end()) return false;
int x = it1->second, y = it2->second, r = root(x), i = index(x), j = index(y);
if (i > j) swap(i, j), swap(x, y);
int A, X, B, Y, C, rest;
split(r, i, A, rest); split(rest, 1, X, rest); split(rest, j - i - 1, B, rest); split(rest, 1, Y, C);
merge(A, C); // B is now a separate tour
arc.erase(it1), arc.erase(it2); freeIds.push_back(x), freeIds.push_back(y); return true;
}
void setVal(int v, ll x) { int y = v + 1; t[y].val = x; for (; y; y = t[y].p) pull(y); }
ll componentSum(int v) const { return t[root(v + 1)].sum; }
int componentSize(int v) const { return t[root(v + 1)].cnt; }
pair<ll, int> subtree(int v, int p) { // {sum, size} of v's side of edge p - v
int r = reroot(p), i = index(arc[{p, v}]), j = index(arc[{v, p}]), A, B, C, rest;
split(r, i + 1, A, rest); split(rest, j - i - 1, B, C);
pair<ll, int> res{t[B].sum, t[B].cnt};
merge(merge(A, B), C); return res;
}
};For lazy updates on whole subtrees (“add to every vertex below edge –”), put a lazy tag on the treap and push it in split, merge and index walks; for minimum / maximum aggregates use the same pattern as sum.
Proof: the tour operations are correct
Tours: in the tour of a tree started at , the DFS enters ‘s subtree by arc and leaves it by arc , visiting exactly that subtree’s vertex and arc nodes in between; so a subtree is a contiguous block. A cyclic rotation of a tour is the tour started at another vertex (the DFS order of a cycle walk around the tree is the same cyclic sequence of arcs), so
rerootis a rotation at the vertex node. Link: with ‘s tour starting at and ‘s at , the sequence (tour of ), , (tour of ), is the tour of the joined tree that visits ‘s side as the last child of . Cut: with the positions of the two arcs, the block strictly between them is the tour of the side not containing the tour’s start (the subtree below the edge), and is the tour of the rest, since removing a child subtree from a tour leaves a tour. Index and root: parent pointers are maintained bypulland cleared at every returned root, so walking up gives the treap root and the in-order index. Every operation performs splits and merges, each expected for a treap of nodes;setValwalks one root path.
| Need | Structure |
|---|---|
| subtree / component aggregates, link and cut | Euler tour tree |
| path aggregates, link and cut | link-cut tree |
| both, or non-local information (diameter, centre) | Top Trees |
| connectivity in a general dynamic graph | HDT: levels of spanning forests stored as Euler tour trees, amortized |
The two structures are complementary, neither subsumes the other: an Euler tour tree is unrooted (there is no evert, rerooting is just a rotation and changes nothing observable) and used inside HDT dynamic connectivity, which needs exactly link, cut, and “find any incident non-tree edge in this subtree”; a link-cut tree is rooted and used for flow speedups and dynamic MST. If the tree is static, a plain Euler tour plus a Fenwick tree gives subtree queries in with far less code; if edges change but everything is offline, segment-tree-on-time is simpler. Euler tour trees earn their complexity only in the genuinely online, genuinely dynamic case.