송신기

면접 대비

시간 제한2초메모리 제한1024 MB

요약

방들이 트리로 연결된 광산에서 모든 터널이 신호를 받도록 와이파이 송신기의 최소 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 트리, 동적 계획법, DFS
정답자: 아직 제출이 없습니다

문제

바이타자르는 역사가 깊은 소금 광산의 새 관리자가 되었다. 관광객을 더 끌어모으려고 그는 광산 통로에 무선 인터넷을 설치하려 한다.

광산은 $n$ 개의 방과 $n - 1$ 개의 통로로 이루어져 있으며, 어느 방에서든 통로를 따라 다른 모든 방으로 갈 수 있다. 바이타자르는 모든 통로에서 인터넷을 쓸 수 있도록 방에 무선 송신기를 놓으려 한다. $a$ 번 방과 $b$ 번 방을 잇는 통로에서 인터넷을 쓰려면 다음 조건 중 하나를 만족해야 한다.

$a$ 번 방 또는 $b$ 번 방에 송신기가 있다.
$a$ 번 방 또는 $b$ 번 방에서 통로를 한 개만 지나 갈 수 있는 방들의 집합에 송신기가 두 대 이상 있다.

바이타자르가 놓아야 하는 송신기의 최소 개수를 구하라. 한 방에 송신기를 원하는 만큼 놓을 수 있다.

입력

첫 줄에 방의 개수를 나타내는 양의 정수 $n$ 이 주어진다. 방은 1번부터 $n$ 번까지 번호가 매겨져 있다.

이어지는 $n - 1$ 개의 줄에는 각각 정수 $a$ 와 $b$ ( $1 \le a, b \le n$ , $a \ne b$ )가 공백 하나로 구분되어 주어지며, 이는 $a$ 번 방과 $b$ 번 방이 통로로 연결되어 있음을 뜻한다.

출력

표준 출력의 첫 줄에 바이타자르가 놓아야 하는 송신기의 최소 개수를 정수 하나로 출력한다.

제한

$n \le 200\,000$

예제2

예제 1
입력
```
7
1 2
2 3
2 4
4 5
5 6
6 7
```
예상 출력
```
2
```
예제 2
입력
```
7
1 2
2 3
4 3
5 4
6 3
7 6
```
예상 출력
```
2
```