Virtual Trees

A virtual tree compresses a large fixed tree around a small set of important vertices. It keeps the selected vertices and the branching points needed to connect them, replacing long chains with weighted edges. Imagine a tree with 200,000 vertices and many queries, each naming just 20 vertices: visiting the entire tree for every query wastes most of the work. After one preprocessing pass, a virtual tree lets each query work mainly with its selected subset.

The compression preserves ancestor relationships and distances between retained vertices exactly. It does not preserve every property of every omitted vertex. Use it for selected-vertex distance calculations, colored-vertex queries, minimal connecting subtrees, and tree DP whose transitions can summarize the omitted paths. This lesson constructs one query’s virtual tree; the preprocessing can be reused for many queries.

Prerequisites: Read Euler Tour of a Tree for DFS intervals and Binary Lifting for O(log N) LCA queries. Familiarity with sorting, stacks, and Tree Dynamic Programming is useful for later applications.

Build the idea

1. Choose the information that must survive

   Root the original tree at vertex 1. Call the query’s distinct selected set S, with K=|S|. The virtual tree retains S and the LCAs that connect its occupied branches. An LCA, or lowest common ancestor, is the deepest vertex that is an ancestor of both endpoints. A retained vertex’s virtual parent is its closest retained strict ancestor. A virtual edge parent→child stands for the complete original path between those vertices, not a newly invented connection.

   A helper LCA is not automatically selected. Keep the distinction when a later DP counts selected items. Also verify that your DP can summarize a compressed path: if every omitted vertex carries a separate decision or value, storing only the path length may be insufficient.

2. Preprocess DFS order and LCA once

   The code uses an iterative DFS, avoiding recursion overflow on a long path. entry[v] is the position when v is first visited. subtreeEnd[v] is the largest entry position inside its subtree; the timer advances only on entry. Therefore a is an ancestor of b exactly when entry[a]≤entry[b]≤subtreeEnd[a]. Do not mix this inclusive interval convention with a different Euler-tour convention.

   depth[v] counts original edges from root 1. ancestorTable[j][v] stores the ancestor 2^j levels above v, with the root pointing to itself. LCA first handles ancestor cases, then lifts one endpoint from the largest jump down. Preprocessing is independent of the selected set, so it should be reused rather than repeated for each query.

3. Add the necessary branching LCAs

   Sort the selected vertices by entry time and remove duplicates. Query the LCA of each adjacent pair in this sorted list, append those LCAs, then sort and deduplicate again. Use the size of the original distinct selected list for the LCA loop; do not start pairing newly appended LCAs in the same loop.

   Why are adjacent pairs sufficient? DFS visits every child subtree as one consecutive block. If a branching vertex joins selected vertices in different child subtrees, the boundary between two occupied blocks contains consecutive selected vertices whose LCA is that branching vertex. Thus every required branching point is added without computing all K² pairs. There are only K−1 adjacent pairs, so the final retained set has at most 2K−1 vertices for K≥1.

4. Connect retained vertices with a stack

   Process the retained set in increasing entry order. The stack contains an ancestor chain. For the next vertex v, pop while the top is not an ancestor of v. If a top remains, it is v’s nearest retained ancestor: add that edge, then push v. Popping finishes a branch; it never deletes its already-built edges.

   All necessary LCAs are present, so the first retained vertex is the LCA of the selected set and all later retained vertices find a parent. The virtual root need not be original root 1. For the path 1–2–3–4–5 with selected set {2,5}, the virtual tree is rooted at 2 and has just edge 2→5 of length 3. Adding root 1 would be an optional convention, not a requirement here.

5. Worked example: retain branches and compress paths

   Use the nine-vertex tree shown below, with selected vertices {4,6,9}. Adjacency-list order in the sample gives DFS order 1,2,4,5,6,3,7,8,9. The selected vertices already occur in order 4,6,9. LCA(4,6)=2 and LCA(6,9)=1, so the retained set in DFS order becomes 1,2,4,6,9. Vertices 1 and 2 are added structural helpers, while 3,5,7,8 are omitted.

   Next vertex	Stack after insertion	New edge and length
   1	[1]	None: virtual root
   2	[1,2]	1→2, length 1
   4	[1,2,4]	2→4, length 1
   6	[1,2,6]	Pop 4; 2→6, length 2
   9	[1,9]	Pop 6 and 2; 1→9, length 4

   The path 2→6 replaces 2–5–6, while 1→9 replaces 1–3–7–8–9. The distance between selected vertices 4 and 9 is 1+1+4=6 in the virtual tree, exactly as in the original. Summing all virtual edge lengths gives 8, the size in edges of the smallest connected subtree containing all three selected vertices.

6. Preserve the right edge information

   Because the parent is an original ancestor, an unweighted virtual edge stores depth[child]−depth[parent]. These compressed paths meet only at retained endpoints. Expanding a virtual path therefore reconstructs the unique original path between its endpoints, which proves distance preservation. For weighted original edges, store rootDistance[child]−rootDistance[parent] instead, using long long for distances when needed; still use ordinary depth to count ancestor jumps.

   Other applications may need a path minimum, maximum, or another aggregate instead of length. The virtual-tree construction stays the same, but that aggregate must come from an appropriate original-tree query structure. Compression does not magically calculate it.

7. Understand the implementation and corner cases

   graph and the DFS arrays describe the original tree. retained begins as the selected list and later contains its LCA closure. ancestors is the construction stack; edges stores parent, child, and compressed length. Output IDs stay 1-based and are ordered by DFS entry time, not numerical label.

   An empty query prints 0 0 and an empty vertex line. A single distinct selected vertex produces one vertex and no edges. Duplicate input IDs do not add new selected items. The program assumes a valid connected undirected tree with N−1 edges and valid vertex labels; an arbitrary graph needs a different model.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int vertexCount,selectedCount;
    cin>>vertexCount>>selectedCount;
    vector<vector<int>>graph(vertexCount+1);
    for(int i=1,u,v;i<vertexCount;i++){
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int levels=1;
    while((1LL<<levels)<=vertexCount){
        ++levels;
    }
    vector<vector<int>>ancestorTable(levels,vector<int>(vertexCount+1));
    vector<int>entry(vertexCount+1),subtreeEnd(vertexCount+1),depth(vertexCount+1);
    vector<tuple<int,int,bool>>events{{1,1,false}};
    int timer=0;
    while(!events.empty()){
        auto[v,p,exit]=events.back();
        events.pop_back();
        if(exit){
            subtreeEnd[v]=timer;
            continue;
        }
        // Root points to itself so ancestor jumps never leave valid vertices.
        entry[v]=++timer;
        ancestorTable[0][v]=p;
        for(int j=1;j<levels;j++){
            ancestorTable[j][v]=ancestorTable[j-1][ancestorTable[j-1][v]];
        }
        events.push_back({v,p,true});
        for(int i=(int)graph[v].size()-1;i>=0;i--){
            int u=graph[v][i];
            if(u==p){
                continue;
            }
            depth[u]=depth[v]+1;
            events.push_back({u,v,false});
        }
    }
    // Inclusive DFS intervals give a constant-time ancestor test.
    auto ancestor=[&](int a,int b){
        return entry[a]<=entry[b]&&entry[b]<=subtreeEnd[a];
    };
    auto lca=[&](int a,int b){
        if(ancestor(a,b)){
            return a;
        }
        if(ancestor(b,a)){
            return b;
        }
        for(int j=levels-1;j>=0;j--){
            if(!ancestor(ancestorTable[j][a],b)){
                a=ancestorTable[j][a];
            }
        }
        return ancestorTable[0][a];
    };
    auto byEntry=[&](int a,int b){
        return entry[a]<entry[b];
    };
    vector<int>retained(selectedCount);
    for(int&v:retained){
        cin>>v;
    }
    sort(retained.begin(),retained.end(),byEntry);
    retained.erase(unique(retained.begin(),retained.end()),retained.end());
    int distinctSelected=(int)retained.size();
    // Only adjacent ORIGINAL important vertices need LCA queries.
    for(int i=1;i<distinctSelected;i++){
        retained.push_back(lca(retained[i-1],retained[i]));
    }
    sort(retained.begin(),retained.end(),byEntry);
    retained.erase(unique(retained.begin(),retained.end()),retained.end());
    vector<int>ancestors;
    vector<tuple<int,int,int>>edges;
    // The stack holds retained ancestors; its top is the virtual parent.
    for(int v:retained){
        while(!ancestors.empty()&&!ancestor(ancestors.back(),v)){
            ancestors.pop_back();
        }
        if(!ancestors.empty()){
            // Preserve the length of the whole compressed original path.
            int p=ancestors.back();
            edges.push_back({p,v,depth[v]-depth[p]});
        }
        ancestors.push_back(v);
    }
    cout<<retained.size()<<' '<<edges.size()<<'\n';
    for(int i=0;i<(int)retained.size();i++){
        if(i){
            cout<<' ';
        }
        cout<<retained[i];
    }
    cout<<'\n';
    for(auto[u,v,w]:edges){
        cout<<u<<' '<<v<<' '<<w<<'\n';
    }
}

Complexity analysis

Let N be the original tree size, K_in the supplied list length, and K the number of distinct selected vertices. One-time preprocessing takes O(N log N) time and space: each vertex fills O(log N) ancestor entries, and adjacency lists use O(N) space. The iterative DFS stack also uses at most O(N) space.

One query takes O(K_in log(K_in+1)+K log N) time and O(K_in) extra space, including its input vector. Initial sorting removes duplicates; K−1 binary-lifting LCA queries cost O(K log N); sorting at most 2K−1 retained vertices costs O(K log(K+1)); stack construction is O(K), since each retained vertex is pushed and popped at most once. When supplied IDs are distinct, this is the usual O(K log K+K log N) bound. The empty query does constant work after preprocessing.

For many queries, keep the preprocessing arrays and allocate only query-sized vectors. Clearing an N-sized visited array for each query would add O(N) per query and defeat the intended bound. With O(1) LCA queries from a different preprocessing method, the K log N term can be removed; this code uses binary lifting.

Example input and output

Read N K (1≤N≤200000, 0≤K≤200000), then N−1 edges of a connected undirected tree on vertices 1..N, then K selected vertex IDs. Duplicates are allowed. The program roots the tree at 1 and prints retained-vertex count and edge count, retained IDs in DFS order, then parent child length for each virtual edge. K=0 still prints an empty second line.

Input

9 3
1 2
1 3
2 4
2 5
5 6
3 7
7 8
8 9
4 6 9

Output

5 4
1 2 4 6 9
1 2 1
2 4 1
2 6 2
1 9 4

The first line counts the three selected vertices plus LCAs 1 and 2. The final two edges compress paths of lengths 2 and 4. Their weights are essential: replacing every compressed length by 1 would give incorrect distances. The worked example above traces every stack change that produces this output.

Practical applications

Use virtual trees when many independent queries involve small vertex subsets and the unselected paths can be summarized. Typical tasks ask for selected-vertex distances, a minimal connecting subtree, or a DP over a single color’s vertices. A query covering almost the entire original tree offers little compression benefit. Revisit Euler Tour of a Tree and Binary Lifting if the preprocessing is unfamiliar.

Check your understanding

What length should virtual edge a→b store in an unweighted original tree?

Put it into practice

Practice: (1) Run the nine-vertex sample and verify that the minimal connecting subtree has length 8. (2) Select {2,5} in the path 1–2–3–4–5; predict both output vertices and the edge weight. (3) Adapt the query phase to print only the sum of virtual edge lengths, preserving the preprocessing for later queries.

Show a hint

Sum the compressed edge lengths: their expanded paths are edge-disjoint and cover the minimal connecting subtree. Keep selected status separate from structural LCAs for any DP that counts selected vertices.

Further reading

• USACO Guide: Virtual Trees ↗