Virtual Tree / Auxiliary Tree
Virtual Tree / Auxiliary Tree
Problem Statement
Given tree with vertices. Process queries of the form . For each query print the sum of the distances for each pair from the given set of vertices. More formally, find
Virtual Tree / Auxiliary Tree
Given tree with vertices. Process queries of the form . For each query print the sum of the distances for each pair from the given set of vertices. More formally, find
where is the distance (number of edges) between vertices and .
Basically, all vertices are included into the set.
The solution is quite simple: find the contribution of each edge and add it to the answer. Complexity is .
Note: this also works for weighted edges if we use edge weights instead of .
For the general case, we introduce a Virtual Tree (Auxiliary Tree) and transform the problem into the special case on a much smaller tree.
Virtual tree for a given set is the minimal set of vertices , such that:
That means for any two vertices , we also have .
As an example, consider the following tree with vertices, and suppose we want to build a virtual tree for the set .
To build an Auxiliary Tree corresponding to a set :
tin).lca to the set.This gives the minimal set closed under LCA, and we can build the virtual tree in overall complexity .
After building the virtual tree, we solve the query using edge contributions.
For a virtual tree edge :
Then this edge contributes to the sum over unordered pairs by:
Since the problem asks for ordered pairs (both and ), multiply by :
So we only need one DFS on the virtual tree to compute all subtree counts and accumulate the answer.
This keeps the total complexity per query at:
void VirtualTree(vector<int> v) {
// sort by DFS traversal order
sort(v.begin(), v.end(), [&](int x, int y) { return tin[x] < tin[y]; });
vector<int> s = v;
for (int i = 1; i < (int)v.size(); i++) {
s.push_back(lca(v[i], v[i - 1]));
}
sort(s.begin(), s.end(), [&](int x, int y) { return tin[x] < tin[y]; });
s.erase(unique(s.begin(), s.end()), s.end()); // delete duplicates
// build edges of the virtual tree using stack
vector<int> st = {s[0]};
for (int i = 1; i < (int)s.size(); i++) {
while (!st.empty() && !is_parent(st.back(), s[i])) {
st.pop_back();
}
add_edge(st.back(), s[i]);
st.push_back(s[i]);
}
}