압축된 생성 부분트리

정점 $n$개로 이루어진 트리 $T$가 있으며, 정점 번호는 1부터 $n$까지이다. 정점 집합 $X$에 속한 정점을 생성된 정점(spanned)이라 하고, $X$에 속하지 않은 정점을 생성되지 않은 정점(not spanned)이라 한다. 압축 생성 부분트리 $S(X)$는 다음 알고리즘으로 구한다.

1. $S(X) \leftarrow T$로 둔다.
2. 생성되지 않은 정점 중 연결된 간선이 정확히 하나인 정점이 있으면, 그 정점을 간선과 함께 제거한다.
3. 2번의 조건이 계속 성립하면 2번을 반복한다.
4. 생성되지 않은 정점 중 연결된 간선이 정확히 두 개인 정점이 있으면, 그 정점과 두 간선을 제거하고 남은 두 끝점을 잇는 새 간선을 추가한다.
5. 4번의 조건이 계속 성립하면 4번을 반복한다.

형식적으로, $S(X)$는 $X$의 모든 정점을 포함하는 $T$의 가장 작은 부분 그래프이며, 나머지 차수가 2 이하인 정점은 펴서 없앤 그래프이다.

테스트 1의 트리와 $X = \{3, 4, 6\}$, $X = \{2, 5, 6\}$일 때의 압축 생성 부분트리이다.

트리 $T$는 주어지지 않는다. 대신 $T$를 찾아야 한다. 다음 형태의 질문을 할 수 있다: "$X$의 압축 생성 부분트리는 정점을 몇 개 포함하는가?" 이 질문만으로는 트리를 찾을 수 없으므로, $T$에는 연결된 간선이 정확히 두 개인 정점이 없다.