Chapter 2 · Trees
Entry/Exit Times and the Euler Tour
Flatten a tree into an array, and get subtree queries, ancestry tests and LCA-from-RMQ for free.
There are two different objects with this name, and mixing them up ruins afternoons:
- Tin/tout (entry–exit, DFS order): tin[u] when u is first visited, tout[u] after its whole subtree is done. Subtree of u = the contiguous interval [tin[u], tout[u]).
- Euler tour of the walk (also called the first-occurrence tour): the length-2n-1 sequence of vertices visited along the DFS walk, including repeats when returning up. Its range minima give LCA.
vector<int> tin(n), tout(n), flat(n); // flat[tin[u]] = u
int timer = 0;
void dfs(int u, int p) {
tin[u] = timer; flat[timer] = u; timer++;
for (int v : g[u]) if (v != p) dfs(v, u);
tout[u] = timer; // half-open: [tin, tout)
}
bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }v lies in the subtree of u ⇔ tin[u] ≤ tin[v] < tout[u] ⇔ [tin[v], tout[v]) ⊆ [tin[u], tout[u]).
DFS enters u, then recursively finishes each child's entire subtree before exiting u; so all times assigned between tin[u] and tout[u] belong to descendants, and nothing outside that window can be a descendant. ∎
#Everything this buys
Add x to every vertex in the subtree of u; query the value at v: one range-add/point-query Fenwick Tree (Binary Indexed Tree) over the flat array. Subtree sum? Range-sum over [tin[u], tout[u]). Both O(log n).
// subtree add, subtree sum: BIT with two arrays (standard trick) or a lazy segtree
bit1.add(tin[u], x); bit1.add(tout[u], -x); // point query at v:
val = bit1.sum(tin[v]);
// sum over a subtree needs the "weighted" version:
add(l, r, x): bitA.add(l, x); bitA.add(r, -x);
bitB.add(l, x*(l-1)); bitB.add(r, -x*r);
prefix(p) = p*sum(bitA, p) - sum(bitB, p);If updates are on vertices/edges and queries are subtree-aggregate, tin/tout + a lazy segment tree is the shortest correct code. The moment queries involve paths (root-to-vertex, u–v), tin/tout alone is not enough: jump to Heavy-Light Decomposition (paths split into O(log n) subtree-queries) or Euler-tour + LCA for root-paths only.
#The 2n−1 tour and RMQ
Walk the tree along the DFS, appending a vertex each time you step onto it (down or up). Length 2n-1. Then:
lca(u,v) is the vertex of minimum depth in the tour between the first occurrences of u and v.
Between the first visit of u and the first visit of v the walk must leave u's branch and climb to their common ancestor; it cannot climb above lca(u,v) without having visited that ancestor later (which would place a shallower vertex inside the interval, and contradict that both are still below it). The vertex where the walk turns around is exactly lca(u,v), and it is the unique shallowest one in the range. ∎
So "LCA in O(1)" reduces to "RMQ in O(1) after O(n log n)", solved by a sparse table (Sparse Table and RMQ) — or O(n) build with the ±1 RMQ trick (LCA via Range Minimum Query).
vector<int> tour, first(n, -1), depth(n);
void dfs(int u, int p, int d) {
first[u] = (int)tour.size(); tour.push_back(u); depth[u] = d;
for (int v : g[u]) if (v != p) {
dfs(v, u, d + 1);
tour.push_back(u); // coming back up
}
}
int lca(int u, int v) {
int l = first[u], r = first[v]; if (l > r) swap(l, r);
return rmq_min_by_depth(l, r); // sparse table over tour[]
}Some references define tout as a third increment ("timer used 2n times"). Then subtree = [tin[u], tout[u]] inclusive, and the interval test changes to tin[u] <= tin[v] && tout[u] >= tout[v]. Pick one convention and write it as a comment in your template — mixed conventions between a is_ancestor helper and a segment tree is a classic 20-minute penalty.