viii. Virtual Tree

For a set $S$ of $k$ marked vertices, the virtual (auxiliary) tree keeps $S$ plus the LCAs needed to preserve their ancestor structure: at most $2k-1$ vertices, each edge standing for a compressed path. Queries with $\sum k\le N$ then run a tree DP in $O(k\log k)$ each instead of $O(n)$.

Construction: sort $S$ by tin, add the LCA of every adjacent pair, sort and deduplicate again; then the virtual parent of each vertex (except the first) is the LCA of it and its predecessor in this order.

pair<vector<int>, vector<int>> virtualTree(const LCA& L, vector<int> vs) {   // {vertices by tin, virtual parent (-1 for root)}
    auto byTin = [&](int a, int b) { return L.tin[a] < L.tin[b]; };
    sort(all(vs), byTin); vs.erase(unique(all(vs)), vs.end());
    for (int i = 0, k = sz(vs); i + 1 < k; i++) vs.push_back(L.lca(vs[i], vs[i + 1]));
    sort(all(vs), byTin); vs.erase(unique(all(vs)), vs.end());
    vector<int> vpar(sz(vs), -1);
    for (int i = 1; i < sz(vs); i++) vpar[i] = L.lca(vs[i - 1], vs[i]);
    return {vs, vpar};                                     // edge (vs[i], vpar[i]) has length dep[vs[i]] - dep[vpar[i]]
}

Process vertices in reverse order of the returned list for bottom-up DP (children come after parents). Keep per-query arrays indexed by vertex id but reset only the touched vertices, never the whole array. Mark which vertices are original (in $S$) versus added LCAs.

// example: cut edges of minimum total weight so that no marked vertex is connected to the root (root not marked)
// mn[v] = minimum edge weight on the root path of v (precomputed once)
ll cutFromRoot(const LCA& L, const vector<ll>& mn, vector<int> S, vector<char>& marked, int root) {
    S.push_back(root);
    auto [vs, vpar] = virtualTree(L, S);
    int k = sz(vs); vector<ll> dp(k); map<int, int> idx; for (int i = 0; i < k; i++) idx[vs[i]] = i;
    for (int i = k - 1; i > 0; i--) {                      // vs[0] is the root (smallest tin)
        int v = vs[i];
        dp[i] = marked[v] ? mn[v] : min(mn[v], dp[i]);    // dp[i] held the children's sum
        dp[idx[vpar[i]]] += dp[i];
    }
    return dp[0];                                          // the root cannot be cut above: sum of children
}

Proof: adjacent LCAs suffice, and the parent formula

Lemma: for $v_1,\dots ,v_k$ sorted by tin, $\text{lca}(v_i,v_j)$ ($i<j$) is the shallowest of $\text{lca}(v_t,v_{t+1})$, $i\le t<j$. Indeed all $v_t$ with $i\le t\le j$ lie in the subtree of $a=\text{lca}(v_i,v_j)$ (its preorder interval contains the tin of both ends), so each adjacent LCA is a descendant of $a$; and the walk $v_i,v_{i+1},\dots ,v_j$ must leave the child subtree of $a$ containing $v_i$ at some step, whose LCA is then $a$. Hence the set $V^{\prime }=S\cup \{\text{adjacent LCAs}\}$ is closed under pairwise LCA (an LCA of LCAs is the LCA of a set of original vertices, i.e. of its min- and max-tin members).

Parent formula: in the sorted closed set, let $a=\text{lca}(v_{i-1},v_i)\in V^{\prime }$. It is an ancestor of $v_i$ and differs from $v_i$ (an ancestor has a smaller tin). Suppose some $x\in V^{\prime }$ lies strictly between $a$ and $v_i$. Then $x$ is not an ancestor of $v_{i-1}$ (it would be a deeper common ancestor), while $v_{i-1}$ is either $a$ or lies in an earlier child subtree of $a$; in both cases $\text{tin}(v_{i-1})<\text{tin}(x)<\text{tin}(v_i)$, contradicting adjacency. So $a$ is the nearest ancestor of $v_i$ in $V^{\prime }$. Size: $|V^{\prime }|\le 2k-1$.

Example DP: to separate a marked $v$ from the root one must cut an edge on its root path, the cheapest costing $\text{mn}[v]$; for an unmarked virtual vertex, either cut above it ($\text{mn}[v]$, which separates its whole subtree) or solve each virtual child independently (their compressed paths are disjoint below $v$, and a single cut above a child’s path is captured by that child’s own $\text{mn}$ since $\text{mn}$ is a prefix minimum). Marked vertices must be cut above themselves.

Related compression techniques

All of these share the same instinct: replace a big structure with a small one that keeps the one property the query needs.

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

Typical uses

Query on a vertex set	Virtual-tree DP
minimum weight to separate all marked vertices from the root	the DP above
sum / min / max of pairwise distances among marked vertices	edge contributions with marked counts; two best depths
number of vertices on the union of paths between marked vertices (Steiner tree size)	sum of virtual edge lengths + 1; equals half the cyclic tour $\sum d(v_i,v_{i+1})$ over sorted $S$
minimum vertices to delete so marked ones are pairwise disconnected	greedy DP counting marked children
for each marked vertex, the nearest other marked vertex	two passes (down then up) on the virtual tree

Proof: Steiner tree size by the cyclic tour

Sort $S$ by tin and close the cycle $v_1,\dots ,v_k,v_1$. The concatenated paths $v_i⇝v_{i+1}$ form the DFS walk of the minimal subtree spanning $S$ (consecutive marked vertices in preorder are joined exactly through the part of the DFS between them), which traverses each edge of that subtree twice and no other edge. So the number of edges is $\frac{1}{2}\sum d(v_i,v_{i+1})$, and the vertex count is one more.