Chapter 10 · Lowest Common Ancestor
Virtual Trees
Build the minimal subtree spanning k marked vertices in O(k log k) with a stack and LCA — the trick behind a hundred "query on a subset of vertices" problems.
Given a rooted tree T and a set S of k marked vertices, the virtual tree widehat T(S) is the tree on the closure overline S = S ∪ {lca(u,v) : u,v ∈ S}, with an edge a → b whenever a is an ancestor of b and no element of overline S lies strictly between them. Path lengths become dist in T, so every question of the form "answer something about the subgraph induced by the paths between marked vertices" can be asked on widehat T(S) instead — on O(k) vertices rather than n.
|overline S| ≤ 2k - 1, and every non-marked vertex of widehat T(S) has at least two children. So widehat T(S) has O(k) vertices and edges.
Root widehat T(S); its leaves are all marked (a leaf that was added as an LCA would have ≥ 2 children by definition). A tree whose m leaves are marked and whose internal nodes have ≥ 2 children has m-1 internal nodes: count edges = nodes - 1 and nodes = m + i with ∑ deg ≥ 2i + m = 2(m+i-1) forcing equality and deg = 2 for every internal node in the "chain-collapsed" sense — by induction on m the claim is immediate (merge two sibling subtrees, each LCA added joins at least two components). Hence i ≤ k-1 and |overline S| = k + i ≤ 2k-1. ∎
#The stack algorithm
Sort S by tin and scan it, maintaining the right spine of the virtual tree built so far. Consecutive elements in tin order share their LCA at the point where the spine must bend; pop until the new vertex fits.
// vertices[0..k) marked, sorted by tin; uses tin/tout, lca from binary lifting
vector<int> build(vector<int> v) {
sort(v.begin(), v.end(), [&](int a, int b) { return tin[a] < tin[b]; });
v.erase(unique(v.begin(), v.end()), v.end());
vector<int> st{ v[0] }, nodes{ v[0] };
for (size_t i = 1; i < v.size(); i++) {
int x = v[i], a = lca(x, st.back());
if (a == st.back()) { st.push_back(x); nodes.push_back(x); continue; }
while (st.size() > 1 && depth[st[st.size()-2]] >= depth[a]) {
add_edge(st[st.size()-2], st.back()); // edge of the virtual tree
st.pop_back();
}
if (st.back() != a) { // a splits the top edge
add_edge(a, st.back()); st.pop_back();
if (nodes.empty() || nodes.back() != a) nodes.push_back(a);
if (st.empty() || st.back() != a) st.push_back(a);
}
st.push_back(x); nodes.push_back(x);
}
while (st.size() > 1) { add_edge(st[st.size()-2], st.back()); st.pop_back(); }
return nodes; // the O(k) vertices, in tin order
}The algorithm outputs widehat T(S) in O(k log k) time (O(k log k) for the sort, O(k) for the scan: each vertex is pushed and popped once, and each lca call is O(log n)).
Invariant: st is the path in T from v0's side down to the most recently processed vertex, restricted to overline S and read from top to bottom — i.e. the right spine. Processing x with a = lca(x, top): every spine vertex strictly below a is finished (no later marked vertex can be in its subtree, since tin order means all of a's subtree containing x comes after, and the processed vertices are in earlier child-subtrees of a). So edges from those vertices to their spine predecessors are final — emitting them on the way out is correct, and a must be inserted because it is now an LCA of two processed marks. When a is already on the spine, popping to it and pushing x keeps the invariant; when a is new (strictly below the second-from-top), splitting the top edge and inserting a does. Finally, draining the stack closes the remaining spine edges, and the last edge lands on the root of widehat T(S).
For the bound: at most 2k-1 vertices are ever pushed, so O(k) pushes/pops and O(k) emitted edges. ∎
- Duplicate marks and marks that are ancestors of other marks: deduplicate before the scan, and allow a ∈ S (else you emit the same vertex twice into
nodes). - You must re-run your DP on widehat T(S) with edge weights distT(a,b), not with unit lengths. "Number of vertices of T on the paths" = sum of dist over virtual edges, or ∑ (edge length -1) for internal-only counts.
- Sorting by
tinrequires the same root as yourtin/tout; if the problem re-roots per query, you must re-root the DP (rerooting, Distance, Radius, Eccentricity), not the tour. - Building the edges lazily inside
add_edgeis where O(k) "extra" work usually hides: clearing the adjacency list of the O(k) vertices after each query needs a touched-list, not a loop over n.
"n,q ≤ 2×105, ∑ k ≤ 2× 105: for each query, given k special vertices, compute the minimum total length of a connected subgraph containing them." On T this is hopeless; on widehat T(S) it is
giving the answer in O(k log k) per query. The classic instance is Codeforces 613D "Ilja and Trees" — exactly "build the virtual tree, DP on it".
- Steiner-tree-ish problems on trees (the "minimum subtree spanning terminals" is just widehat T(S)),
- dynamic connectivity on a tree with k updates per operation: run the query on the virtual tree of updated vertices,
- "sum over all pairs of marked vertices of lca" — one DFS on widehat T(S) with subtree counts,
- divide over marks: some geometry-on-tree problems (diameter of a set, radius of a set) become two DFS passes on the virtual tree; the diameter of S is realised by two leaves of widehat T(S), which is why a single scan in
tinorder suffices (same argument as Tree Diameter in Two Passes for the rotating-calipers-free version).