Given a base tree and a subset of its nodes, the virtual tree preserves the ancestral relationships among these nodes by including all pairwise LCAs and cnonecting them appropriately. This structure maintains relative node relationships while being linear in size relative to the input set.

When nodes are sorted by their Euler tour order, the set of LCAs corresponds to all adjacent pairs in this sequence. This allows efficient LCA computasion using Euler tour with ST tables. The virtual tree's size remains proportional to the input set.

For a node set of size m, we can construct the virtual tree in O(m log m) time. The algorithm typically includes a root node for easier implementation, which can be removed if necessary.

The construction process simulates DFS traversal using a stack that maintains virtual tree nodes in dfn order. For each new node:

1. If its LCA with the stack top equals the stack top, push it directly (descendant relationship)
2. Otherwise, process existing stack nodes until reaching the LCA's level, connect edges, then push remaining nodes

Here's an implementation:

bool nodeCompare(int x, int y) { return dfsOrder[x] < dfsOrder[y]; }
int nodeStack[MAX_N], stackPtr = 0;
vector<int> childNodes[MAX_N + 1];

void buildVirtualTree(vector<int> &nodes) {
    sort(nodes.begin(), nodes.end(), nodeCompare);
    nodeStack[stackPtr++] = ROOT_NODE;
    
    for (auto node : nodes) {
        int ancestor = findLCA(nodeStack[stackPtr-1], node);
        if (ancestor != nodeStack[stackPtr-1]) {
            while (dfsOrder[ancestor] < dfsOrder[nodeStack[stackPtr-2]]) {
                childNodes[nodeStack[stackPtr-2]].push_back(nodeStack[stackPtr-1]);
                stackPtr--;
            }
            childNodes[ancestor].push_back(nodeStack[--stackPtr]);
            if (ancestor != nodeStack[stackPtr-1]) nodeStack[stackPtr++] = ancestor;
        }
        nodeStack[stackPtr++] = node;
    }
    
    while (stackPtr > 1) {
        childNodes[nodeStack[stackPtr-2]].push_back(nodeStack[stackPtr-1]);
        stackPtr--;
    }
    stackPtr--;
}

An alternative approach precomputes all necessary LCAs upfront, simplifying edge connections during stack processing:

void optimizedVirtualTree(vector<int> &nodes) {
    for (auto node : nodes) marked[node] = true;
    nodes.push_back(ROOT_NODE);
    sort(nodes.begin(), nodes.end(), nodeCompare);
    
    int initialSize = nodes.size();
    for (int i = 0; i < initialSize - 1; i++)
        nodes.push_back(findLCA(nodes[i], nodes[i+1]));
    
    sort(nodes.begin(), nodes.end(), nodeCompare);
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
    
    stackPtr = 0;
    for (auto node : nodes) {
        while (stackPtr && !(dfsOrder[nodeStack[stackPtr-1]] <= dfsOrder[node] 
                          && dfsOrder[node] <= maxDfsOrder[nodeStack[stackPtr-1]]))
            stackPtr--;
        
        if (stackPtr) childNodes[nodeStack[stackPtr-1]].push_back(node);
        nodeStack[stackPtr++] = node;
    }
}

Virtual trees enable efficient processing of tree queries involving dynamic node subsets, supporting operations like DP or centroid decmoposition while maintaining the original tree's structural properties. Edge cases may require handling path queries between virtual nodes.