Compressed Spanning Subtrees

Consider a tree $T$ with $n$ vertices numbered from 1 to $n$. For a set $X$ of spanned vertices (vertices not in $X$ are called not spanned), the compressed spanning subtree $S(X)$ is computed as follows.

1. Set $S(X) \leftarrow T$.
2. If a not spanned vertex has exactly one incident edge, remove it together with that edge.
3. Repeat step 2 while the condition still holds.
4. If a not spanned vertex has exactly two incident edges, remove it together with both edges and add a new edge connecting the two other endpoints.
5. Repeat step 4 while the condition still holds.

Formally, $S(X)$ is the smallest subgraph of $T$ that contains all vertices of $X$, after every other vertex of degree two or less is smoothed out.

The tree from test 1, and its compressed spanning subtrees for $X = \{3, 4, 6\}$ and $X = \{2, 5, 6\}$.

The tree $T$ is not given to you. Your task is to find it. You can ask questions of this form: "How many vertices does the compressed spanning subtree of $X$ contain?" Without a guarantee, finding the tree this way would be impossible, so $T$ has no vertex with exactly two incident edges.