시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB509723.333%

문제

새롭고 놀라운 가지를 교배하는 가지 연구원 민규는 여러가지 가지를 교배하여 슈퍼 가지를 만들었다! 민규는 즉시 슈퍼 가지를 기르는 농장을 만들었고, 슈퍼 가지들은 열심히 자라서 수확할 시간이 되었다.

민규의 농장은 $1$번에서 $N$번까지 번호가 붙은 $N$개의 토지와 그 토지들을 잇는 길이 $1$의 도로 $N-1$개로 이루어져 있다. 어느 토지에서든 도로를 통해서 다른 모든 토지로 갈 수 있고, 오직 하나의 토지와 도로로 직접 연결되어 있는 비옥한 토지에만 민규가 슈퍼 가지를 심었다. 단, $1$번 토지에는 창고가 있기 때문에 슈퍼 가지를 절대 심지 않는다.

예제 $1$의 농장. 원형이 토지, 녹색이 창고, 보라색이 가지를 심은 토지이다.

민규는 현재 $1$번 토지에 있고, 민규는 민규가 있는 토지와 연결되어 있는 도로 중 하나를 통해서 움직일 수 있다. 민규가 슈퍼 가지가 심어져 있는 토지에 도착하게 되면 슈퍼 가지를 수확할 수 있고, 수확한 슈퍼 가지를 들고 다시 움직이게 된다. 하지만, 슈퍼 가지들을 안전하게 보관하기 위해 민규는 한번에 슈퍼 가지를 최대 $3$개씩만 들고 움직일 수 있다. 민규가 창고가 위치해 있는 $1$번 토지에 도착하게 된다면, 현재 민규가 들고 있는 슈퍼 가지를 모두 저장할 수 있다. 즉, 민규는 다시 $3$개의 슈퍼 가지를 들 수 있게 된다.

민규는 농장에서 자란 모든 슈퍼 가지를 최대한 빨리 수확해 창고에 저장하려고 한다. 민규가 모든 슈퍼 가지를 수확하여 창고에 저장하려 할 때 움직여야 하는 총 거리의 최솟값을 구하자.

입력

첫째 줄에 농장의 토지 개수 $N$이 주어진다. $(2 \le N \le 10\,000)$

둘째 줄부터 $N - 1$개의 줄에 걸쳐 양의 정수 $a$와 $b$가 주어진다. 이는 $a$번 토지와 $b$번 토지를 연결하는 길이 $1$의 도로가 존재한다는 정보를 나타낸다. $(1 \le a,b \le N;$ $a \ne b)$ 두 토지를 연결하는 도로는 최대 하나뿐이다.

출력

첫째 줄에 민규가 모든 가지를 수확해 창고에 저장하기 위해 움직여야 하는 거리의 최솟값을 출력한다.

예제 입력 1

11
1 2
1 3
3 4
3 5
1 6
6 7
7 8
7 9
6 10
6 11

예제 출력 1

22

$1$번 예제에서 다음과 같이 슈퍼 가지를 수확한다면 $22$번 움직여 모든 슈퍼 가지를 수확할 수 있다.

  1. $2$번 토지에 있는 슈퍼 가지를 수확하고 창고에 돌아와 저장한다.
  2. $4$번 토지와 $5$번 토지를 수확하고 창고에 돌아와 저장한다.
  3. $8$번 토지와 $9$번 토지를 수확하고 창고에 돌아와 저장한다.
  4. $10$번 토지와 $11$번 토지를 수확하고 창고에 돌아와 저장한다.

$22$번보다 적게 움직여 모든 슈퍼 가지를 저장하는 방법은 없음을 보일 수 있다.

출처

Contest > BOJ User Contest > 가지컵 > 2023 가지컵 L번