예제를 트리로 그리면 다음과 같습니다.

1 - 2 - 3

  |    |- 4

  |- 5

이 트리의 구조에서 높이1인 트리를 만들려면 다음과 같은 방법이 있다고 생각합니다.

1) 2번정점에서 3,4와의 간선을 끊음

2) 1번정점과 2번정점과의 간선을 끊음

1번의 경우 트리 구조는 다음과 같이 됩니다.

1 - 2     3        4

   |-5

2번의 경우 트리 구조는 다음과 같이 됩니다.

1 - 5        2 - 3

                 |-4

둘 다 높이를 1에 만족하므로, 2번의 경우가 더 비용이 싸다고 생각합니다.

혹시 문제를 이렇게 이해하는것이 맞는지 질문 드립니다!