고품질 트리

이진 탐색 트리는 컴퓨터 과학에서 가장 유용한 자료구조 중 하나이다. 트리를 균형 있게 유지하는 방법은 여러 가지가 있다. 회전을 사용하는 방법(AVL 트리 등)이나 무작위성을 사용하는 방법(treap 등)이 대표적이다. 그러나 이 방법들은 모두 다소 느리고 복잡하다.

컴퓨터 과학자 Rob은 뿌리 있는 이진 트리를 균형 있게 유지하는 새로운 방법을 고안했다. 이 방법은 현재 최선의 방법보다 훨씬 낫다. 핵심 아이디어는 Rob이 robbery라고 부르는 연산을 반복해서 수행하는 것이다. 로버리 한 번은 트리에서 리프 하나를 골라 제거하는 것이다. Rob은 적절한 시점에 로버리를 적용해서 트리를 $\mathcal{O}(1)$ 분할 상환 시간에 균형 상태로 유지한다.

일부 사람들은 트리에서 원소를 제거하면 알고리즘이 틀리게 된다며 Rob의 획기적인 발견을 비판했다. Rob은 이것이 큰 문제라고 보지 않는다. $2 \cdot 10^5$개의 수를 저장하려는 경우라면 아마 그 수들을 모두 보관할 필요는 없을 것이기 때문이다. 다만 Rob은 이 비판을 받아들이고, 로버리 횟수를 최소로 줄이는 방법을 찾기로 했다.

그림 H.1: 예제 입력 2의 그림이다. 빨간색으로 표시된 정점 3개($4$, $5$, $10$)를 제거하면 트리가 강하게 균형 잡힌 상태가 된다. 이는 트리를 강하게 균형 잡히게 만들기 위해 제거해야 하는 정점의 최소 개수이다.

루트가 정점 $1$인, 정점이 $n$개인 뿌리 있는 이진 트리가 주어진다. 정점은 $1$부터 $n$까지 번호가 매겨져 있다. 트리의 모든 부분 트리가 균형 잡혀 있으면 그 트리를 강하게 균형 잡힌 트리라고 한다. 트리를 강하게 균형 잡힌 상태로 만들기 위해 필요한 로버리의 최소 횟수를 구하라. 뿌리 있는 이진 트리는 왼쪽 부분 트리와 오른쪽 부분 트리의 깊이 차이가 1 이하이면 균형 잡혀 있다고 한다. 로버리는 리프를 제거하는 것이며, 그 결과 부모 정점이 리프가 될 수 있다.

입력은 다음과 같이 주어진다.

• 첫 줄에 정수 $n$ ($1 \leq n \leq 2 \cdot 10^5$)이 주어진다. 이는 트리의 정점 개수이다.
• 이어서 $n-1$개의 줄에 각각 정수 $u$와 $v$ ($1 \leq u, v \leq n$, $u\neq v$)가 주어진다. 이는 정점 $u$와 $v$ 사이의 간선을 뜻한다.

주어지는 간선들은 루트가 정점 $1$인 올바른 이진 트리를 이룬다. 간선은 어떤 순서로 나타나도 되며 방향이 없다. 즉 $u$가 $v$의 부모일 수도 있고, 그 반대일 수도 있다.

트리를 강하게 균형 잡힌 상태로 만들기 위해 제거해야 하는 리프의 최소 개수를 출력한다.