Informatica Online Judge

  벌목기 [1694 / 069E]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 10   Total Tried : 11


The Champion of this Problem (C++) : gs14046 - ms / 485byte
My Best Submission (C++) : N/A

[koistudy.net (33rd 김동규)]

Background

누군가 조종하는 벌목기가 나타났다!
누가 조종하는지는 모르겠으나, 어쨌든 이 벌목기는 트리들을 무자비하게 잘라버리기 시작했다!!

벌목기를 많이 봐 온 우리 경기과학고 학생들은 다음과 같은 규칙을 찾아냈다.

벌목기는 특정 두 노드 사이의 간선을 잘라 제거해 버린다.
그리고 벌목기는 트리를 잘라서 그 부분들이 모두 차수가 "2"이하가 되도록 한다.
벌목기는 언제 죽음을 당할지 모르기 때문에 한시라도 빨리 트리들을 자르려 한다.
즉, 벌목기는 최소한의 횟수로 트리를 직선 형태의 부분들로 잘라놓는다.

벌목기는 트리를 자르기 위해 최소 몇 번을 잘라야 할까?
벌목기를 잘 알고 있는 여러분들이 대답해보자.

Input

첫 줄에는 벌목기가 자르려는 트리의 노드의 개수 N(1<=N<=5e5)이 주어진다.
각 노드들은 1부터 N까지 번호가 매겨져 있다.
그 다음 N-1개의 줄에는 간선으로 연결되는 두 노드의 정보 a, b(1<=a, b<=N)가 주어진다.

Output

벌목기가 규칙을 만족하면서 트리를 자르는 최소 횟수를 출력한다.

IO Example

입력
7
1 2
2 3
3 4
4 5
2 6
4 7

출력
2

예제 설명
2와 6, 4와 7 사이의 간선을 자르면 된다.
여러 가지 방법이 존재한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]