Virtual Tree

For this set, we need to compute the sum of distances over all pairs of chosen vertices:

where $d(x, y)$ is the distance, that is, the number of edges on the path between $x$ and $y$.

Idea

Special Case: $k = N$

If all vertices of the tree are included in the query, then the problem becomes much simpler.

We can compute the contribution of each edge independently and add all contributions to the answer.

This leads to an $O(N)$ solution.

This idea also works for weighted trees.

General Case: $k < N$

In the general case, we do not want to process the entire tree for every query.

Instead, we build a virtual tree (also called an auxiliary tree) for the queried vertices and reduce the problem to a much smaller tree.

Definition of Virtual Tree

Given a set of vertices

the virtual tree is the minimal set of vertices

such that $S$ is closed under the LCA operation.

That means:

• for any two vertices $u, v \in S$, their lowest common ancestor $\mathrm{LCA}(u, v)$ also belongs to $S$.

So the virtual tree consists only of:

• the queried vertices;
• the LCAs needed to connect them.

This makes it much smaller than the original tree.

As an example, consider the following tree with $8$ vertices, and suppose we want to build the virtual tree for the set

How to Build the Virtual Tree

To build the virtual tree for a set $V$:

1. sort all vertices in $V$ by DFS entry time;
2. for every adjacent pair in this order, add their LCA to the set;
3. sort the resulting set again by DFS entry time;
4. remove duplicates;
5. connect the vertices using a stack.

The stack construction works because the vertices are processed in DFS order.

The total complexity of building the virtual tree is:

assuming LCA queries are already available.

Implementation