바이러스

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

요약

이진 트리에서 매 시점마다 한 노드를 백신으로 보호할 수 있을 때 최종적으로 감염되는 노드 수의 최솟값을 구한다.

난이도: 어려움10점 중 8점
유형: 트리, 동적 계획법, 그리디, DFS
정답자: 아직 제출이 없습니다

문제

컴퓨터 바이러스가 이진 트리 모양의 네트워크로 퍼진다. 감염과 방어는 다음 과정을 따른다.

시각 0에 바이러스가 루트를 감염시킨다.
그 뒤 각 시각마다 두 가지 일이 순서대로 일어난다. 먼저 감염되지 않은 노드 하나를 백신으로 방어할 수 있다. 그다음 바이러스가 감염된 모든 노드에서 방어되지 않은 자식 노드 전체로 퍼진다. 한 번 감염되거나 방어된 노드의 상태는 과정이 끝날 때까지 그대로 남는다.
바이러스가 더 퍼질 수 없으면 과정이 끝난다.

한 시각에 방어할 수 있는 노드는 최대 하나이고, 아무 노드도 방어하지 않아도 된다.

목표는 과정이 끝났을 때 감염된 노드의 수를 최소로 만드는 것이다.

네트워크 예시

위 그림의 네트워크에서 노드 1의 자식은 2와 3, 노드 2의 자식은 4 하나, 노드 3의 자식은 5와 6이다. 시각 0에 바이러스가 루트인 노드 1을 감염시킨다. 시각 1에 노드 3을 방어하면 바이러스는 노드 2를 감염시킨다. 이어서 시각 2에 노드 4를 방어하면 바이러스가 더 퍼질 수 없고, 감염된 노드는 2개다. 시각 1에 노드 3 대신 노드 2를 방어하면 바이러스가 노드 3을 감염시키는데, 이때도 감염된 노드는 2개보다 적어지지 않는다. 따라서 이 네트워크의 최솟값은 2다.

이진 트리로 주어진 네트워크에서 감염된 노드 수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 $n$ ( $1 \le n < 2^{20}$ )이 주어진다. 이어지는 $n$ 개 줄 중 $i$ 번째 줄에는 노드 $i$ 의 왼쪽 자식과 오른쪽 자식을 나타내는 정수 두 개가 주어진다. 노드에는 1번부터 $n$ 번까지 번호가 붙어 있고, 루트는 노드 1이며, 자식이 없으면 0으로 나타낸다.

출력

감염된 노드 수의 최솟값을 한 줄에 출력한다.

예제7

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