34709번 - 트리 펴기

문제

$N$개의 정점과 $N-1$개의 간선으로 구성된 트리가 주어진다. 트리의 각 정점에는 1ドル$부터 $N$까지의 번호가 중복 없이 매겨져 있다.

동건이는 트리에 아래와 같은 작업을 할 수 있다. 한 번의 작업은 아래의 두 단계를 순서대로 수행하는 것을 의미한다.

1. 트리에서 이웃한 두 정점 $s$와 $t$를 선택하여 $s$와 $t$를 잇는 간선을 삭제한다. 간선 삭제 후, $s$가 포함된 트리를 $S,ドル $t$가 포함된 트리를 $T$라 하자.
2. 트리 $T$에서 정점 $p$를 선택하고, $p$와 $s$를 잇는 간선을 추가한다.

위의 작업은 항상 트리 상태를 유지한다. 동건이가 주어진 트리를 일자-트리$^\dagger$로 만드는 데 필요한 최소 작업 횟수를 구해보자.

$^\dagger$ 일자-트리란 모든 정점의 차수가 2ドル$ 이하인 트리이다.

입력

첫째 줄에 트리의 정점 개수를 나타내는 정수 $N$이 주어진다. (2ドル \le N \le 500,000円$)

둘째 줄부터 $N-1$개의 줄에 걸쳐 트리를 이루는 간선의 정보를 나타내는 두 정수 $u,ドル $v$가 공백으로 구분되어 주어진다. 이는 $u$번 정점과 $v$번 정점을 잇는 간선이 존재한다는 의미이다. (1ドル \le u, v \le N,ドル $u \ne v$)

입력으로 주어지는 그래프는 항상 트리임이 보장된다.

출력

첫째 줄에 동건이가 주어진 트리를 일자-트리로 만드는 데 필요한 최소 작업 횟수를 출력한다.

제한

노트