Virtual Tree
Compress a query's marked nodes and the LCAs between them into a much smaller tree that preserves the relevant paths.
Virtual Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Virtual tree is the standard way to avoid touching an entire tree when a query only mentions a small set of marked vertices. It builds the smallest tree that still contains all marked vertices and all paths between them.
When to Use It
Use it when:
the base graph is a tree,
each query marks a relatively small subset of vertices,
the needed computation depends only on paths between marked nodes.
Core Idea
Take the marked vertices, sort them by Euler-tour entry time, add the LCAs of consecutive marked vertices, sort and deduplicate again, then connect them with a stack using ancestor relationships.
The resulting compressed tree has only \(O(k)\) vertices for a query with \(k\) marked nodes.
Key Insight
On a tree, the only extra vertices you need are LCAs. Nothing else is necessary to preserve the path structure between the marked nodes. That is why the virtual tree stays small.
Worked Problem
Problem.
Each query gives \(k\) special cities in a country road tree. Compute some DP over the union of paths connecting those cities, for example the minimum number of checkpoints to separate all special cities from each other.
Why virtual tree fits.
The answer only depends on the Steiner tree of the special cities. The virtual tree is exactly that structure in a form that is easy to DP over.
Correctness Intuition
Sorting by Euler time means ancestor intervals are nested correctly. The stack connects each node to the nearest earlier node that is its ancestor in the compressed set, which is exactly the parent it has in the minimal path-preserving tree.
Complexity Analysis
If a query marks \(k\) nodes, building the virtual tree costs \(O(k \log k)\) with ordinary sorting, plus \(O(1)\) or \(O(\log n)\) per LCA depending on the chosen LCA structure.
Implementation
The sample code assumes you already have:
Euler entry times
tin,an
lca(u, v)routine,an
is_ancestor(u, v)test.It returns the compressed node list and the virtual-tree adjacency.
Common Pitfalls
Forgetting to insert LCAs before building the stack.
Building edges in the original-tree depth order instead of Euler order.
Reusing adjacency from one query without clearing it.
Variants / Extensions
Weighted virtual edges storing original-tree distance.
Query-by-query DP on marked nodes.
Combining with centroid or HLD preprocessing around the base tree.
Practice Problems
DP on marked nodes of a tree.
Count or optimize over the union of marked-node paths.
Queries where \(k \ll n\) and the full tree is too expensive per query.
References
Code
Contest-ready reference implementation for the idea explained above.
struct VirtualTree {
vector<int> nodes;
vector<vector<int>> children;
};
VirtualTree build_virtual_tree(
vector<int> marked,
const vector<int>& tin,
const function<int(int, int)>& lca,
const function<bool(int, int)>& is_ancestor
) {
auto by_tin = [&](int a, int b) { return tin[a] < tin[b]; };
sort(marked.begin(), marked.end(), by_tin);
vector<int> nodes = marked;
for (int i = 0; i + 1 < (int)marked.size(); ++i) {
nodes.push_back(lca(marked[i], marked[i + 1]));
}
sort(nodes.begin(), nodes.end(), by_tin);
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
vector<int> st;
vector<vector<int>> children(nodes.size());
unordered_map<int, int> id;
for (int i = 0; i < (int)nodes.size(); ++i) id[nodes[i]] = i;
for (int v : nodes) {
while (!st.empty() && !is_ancestor(st.back(), v)) st.pop_back();
if (!st.empty()) children[id[st.back()]].push_back(id[v]);
st.push_back(v);
}
return {nodes, children};
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.