Virtual Tree

Given a set of $k$ important vertices in a tree of $n$ vertices, build a compressed tree on $O(k)$ nodes that preserves all the ancestor relationships among them. Then run your algorithm on the small tree instead of the big one.

Why it exists

A common problem shape: “you are given $q$ queries, each with a set of vertices $S_i$, and $\sum |S_i|\le 2\cdot 10^5$.” A per-query $O(n)$ tree DP is $O(nq)$ — far too slow. The virtual tree makes each query $O(|S_i|\log n)$, so the total is near-linear.

The construction

1. Sort the important vertices by DFS entry time tin.
2. Add the LCA of each adjacent pair in that order. These are the only extra vertices needed — a fact worth remembering, and the reason the tree stays $O(k)$.
3. Sort the combined set by tin again and deduplicate.
4. Build the tree with a stack: for each vertex in order, pop until the stack top is an ancestor, then attach.

vector<int> buildVirtualTree(vector<int> vs) {
    sort(vs.begin(), vs.end(), [](int a, int b){ return tin[a] < tin[b]; });
    int k = vs.size();
    for (int i = 0; i + 1 < k; i++) vs.push_back(lca(vs[i], vs[i+1]));
    sort(vs.begin(), vs.end(), [](int a, int b){ return tin[a] < tin[b]; });
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
 
    for (int v : vs) vadj[v].clear();
    vector<int> st;
    for (int v : vs) {
        while (!st.empty() && !isAncestor(st.back(), v)) st.pop_back();
        if (!st.empty()) { vadj[st.back()].push_back(v); vpar[v] = st.back(); }
        st.push_back(v);
    }
    return vs;                                    // vs[0] is the root
}
 
bool isAncestor(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }

Clear only the vertices you used (for (int v : vs) vadj[v].clear()), never the whole array — otherwise each query costs $O(n)$ and you have gained nothing.

Why adjacent-pair LCAs suffice

The virtual tree must contain every vertex where two important subtrees branch apart. In DFS order, any such branching vertex is the LCA of two consecutive important vertices — if $u$ and $w$ branch at $x$, then some consecutive pair in between also has $x$ as its LCA. So $k-1$ LCAs are enough, giving at most $2k-1$ vertices total.

Carrying edge information

A virtual edge $(u,v)$ represents a whole path in the original tree. Store what the DP needs:

int weight = dep[v] - dep[u];                     // number of original edges
long long cost = distToRoot[v] - distToRoot[u];   // path weight

Also record whether the endpoints are important or merely LCA helpers — the DP usually treats them differently.

Typical problems

Problem	Virtual tree DP
Minimum cost to disconnect the important vertices from the root	tree DP with min(edge cost, sum of children)
Sum of pairwise distances among the important vertices	edge-contribution DP
Number of paths between important vertices passing through each vertex	subtree counts
Closest important vertex to each important vertex	two-pass DP
Whether the important vertices form a connected subtree	check the virtual tree’s structure

Complexity

• Preprocessing (once): $O(n\log n)$ for LCA.
• Per query: $O(k\log k)$ for sorting plus $O(k\log n)$ for the LCAs.
• Total over all queries: $O(n\log n+(\sum k)\log n)$.

Related compression techniques

Technique	Compresses	Preserves
Virtual tree	a vertex subset	ancestor relationships
Condensation	SCCs	reachability
Bridge tree	2-edge-connected components	edge connectivity
Block-cut tree	biconnected components	vertex connectivity
Centroid decomposition	the whole tree	path structure, $O(\log n)$ depth

All five share the same instinct: replace a big structure with a small one that keeps the property you care about.

See also: LCA · Tree DP · Euler Tour