---
title: "Virtual Trees"
summary: 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.
difficulty: hard
tags: [stack, queries, trees, lca]
time: k log k per query
prereq: [lca/binary-lifting, trees/euler-tour]
see: [advanced-tree/small-to-large, trees/euler-tour]
---

:::definition label="The virtual tree"
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 \cup \{\operatorname{lca}(u,v) : u,v \in S\}$, with an edge $a \to b$ whenever $a$ is an ancestor of $b$ and no element of $\overline S$ lies strictly between them. Path lengths become $\operatorname{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$.
:::

:::lemma title="Size and structure"
$|\overline S| \le 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.
:::

:::proof
Root $\widehat T(S)$; its leaves are all marked (a leaf that was added as an LCA would have $\ge 2$ children by definition). A tree whose $m$ leaves are marked and whose internal nodes have $\ge 2$ children has $m-1$ internal nodes: count edges $= \text{nodes} - 1$ and nodes $= m + i$ with $\sum \deg \ge 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 \le k-1$ and $|\overline S| = k + i \le 2k-1$. ∎
:::

## The stack algorithm
:::idea
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.
:::

```cpp virtual-tree.cpp
// 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
}
```

:::theorem title="Correctness and cost"
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)$).
:::

:::proof
Invariant: `st` is the path in $T$ from $v_0$'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 = \operatorname{lca}(x, \text{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. ∎
:::

:::warning title="Four things that break virtual-tree solutions"
1. **Duplicate marks** and marks that are ancestors of other marks: deduplicate *before* the scan, and allow $a \in S$ (else you emit the same vertex twice into `nodes`).
2. **You must re-run your DP on $\widehat T(S)$ with edge weights $\operatorname{dist}_T(a,b)$**, not with unit lengths. "Number of vertices of $T$ on the paths" = sum of $\operatorname{dist}$ over virtual edges, or $\sum$ (edge length $-1$) for internal-only counts.
3. **Sorting by `tin` requires the same root** as your `tin`/`tout`; if the problem re-roots per query, you must re-root the DP (rerooting, @trees/distance), not the tour.
4. Building the edges lazily inside `add_edge` is 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$.
:::

:::example title="What it buys"
"$n,q \le 2\times10^5$, $\sum k \le 2\times 10^5$: 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
$$\tfrac12 \sum_{(a,b) \in E(\widehat T)} \operatorname{dist}(a,b) \times 2 \;/\; 1 = \sum \operatorname{dist}(\text{each virtual edge}) \quad\text{with the "double the tree, halve" argument,}\;$$
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".
:::

:::note title="Where else this pattern appears"
- **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 $\operatorname{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 `tin` order suffices (same argument as @trees/diameter for the rotating-calipers-free version).
:::

:::problems
- [[CSES 1136]] Counting Paths | https://cses.fi/problemset/task/1136 | core | the "many paths on a tree" pattern with a difference array — the offline sibling of virtual trees
- [[CSES 1137]] Subtree Queries | https://cses.fi/problemset/task/1137 | easy | the flattening that makes the virtual-tree idea natural
:::