다중 엔딩 스토리

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

요약

예와 아니오로 갈리는 이진 분기 구조에서 엔딩 N개를 모두 보는 최소 시간을 구합니다. 한 걸음은 1분이고 퀵 세이브는 한 곳만 기억됩니다.

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

문제

당신은 미소녀 게임(연애 시뮬레이션 게임의 하위 장르)을 사랑하는 프로그래머다. 어제 발매된 'I * C * P * C!'라는 게임이 방금 도착했다. 이 게임에는 여러 개의 엔딩이 있다. 모든 엔딩을 보면 메인 히로인 사쿠야의 특별한 일러스트를 얻을 수 있다. 당장 게임을 시작하고 싶지만, 먼저 모든 엔딩을 가장 짧은 시간에 보는 방법부터 생각해 보자.

이 게임의 분기점은 모두 '예'와 '아니오' 중 하나를 고르는 이지선다다. 한 번 다른 선택지를 고르면 갈라진 이야기는 서로 다른 엔딩으로 이어지고, 다시는 합쳐지지 않는다. 즉 이진 트리 구조다. 분기점에서 다른 분기점이나 엔딩까지 가는 데 정확히 1분이 걸린다. 게임의 처음으로 돌아가는 '리셋'과 처음부터 첫 번째 분기점까지 진행하는 데는 시간이 거의 들지 않는다.

이 게임에는 완료 시간을 크게 줄여 주는 '퀵 세이브' 기능이 있다. 현재 플레이 중인 지점을 기록해 두면, 나중에 언제든 그 지점으로 돌아갈 수 있다. 기록은 여러 번 할 수 있지만, 보관할 수 있는 지점은 마지막으로 기록한 하나뿐이다. 퀵 세이브를 하면 이전 기록은 덮어써진다. 덮어써진 지점으로 돌아가려면 처음부터 다시 플레이해야 한다.

모든 엔딩을 가장 짧은 시간에 완료하는 데 걸리는 시간을 구하라.

입력

첫 줄에 엔딩의 개수 $N$ ( $2 \leq N \leq 500{,}000$ )이 주어진다. 이어서 $N-1$ 개의 줄에 분기점이 주어진다. $i$ 번째 줄은 ID가 $i$ 인 분기점을 나타내며, 두 정수 $Yes_i$ 와 $No_i$ 가 주어진다. 이는 각각 '예'와 '아니오'를 골랐을 때 이어지는 분기점의 ID다. $Yes_i = N$ 이면 '예'를 골랐을 때 바로 엔딩에 도달한다는 뜻이다. $No_i = N$ 도 같은 방식이다. ID가 1인 분기점이 첫 번째 분기점이다. 모든 $i$ 에 대해 $i + 1 \leq Yes_i, No_i \leq N$ 이다. ID가 2 이상 $N-1$ 이하인 분기점은 모든 $Yes_i$ 와 $No_i$ 안에서 정확히 한 번씩 나타난다.

출력

가장 짧은 시간을 한 줄에 출력한다.

예제2

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