광산 지진

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

요약

n개의 홀이 트리 구조로 연결되어 있을 때, 임의의 홀에서 출발해 모든 홀을 방문하면서 각 홀에 도착하는 시간의 합을 최소로 만드는 값을 구합니다.

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

문제

모라비아의 버려진 드워프 광산에 설치된 완전 자율 소형 양조장은 드워프 공학의 솜씨를 보여 준다. 지진이 나면 광산이 흔들려 파이프와 깔때기가 어긋나고, 귀한 액체가 바닥에 쏟아지곤 한다. 양조장 안전 총책임자인 당신은 지진이 일어나면 모든 홀의 기계를 꺼야 한다.

터널을 걸으면 시간이 걸리므로 많은 기계에 늦게 도착할 수밖에 없다. 이는 피할 수 없지만, 쏟아지는 액체의 총량은 최대한 줄이고 싶다.

광산은 $n$ 개의 홀이 $n-1$ 개의 터널로 연결되어 있다. 전체 시스템이 연결되어 있어서 어떤 홀에서든 다른 모든 홀로 갈 수 있다. 터널 하나를 지나는 데 1 단위 시간이 걸린다. 기계를 끄는 것과 홀을 지나는 것은 시간이 걸리지 않는다. 지진 이후 $t$ 단위 시간에 홀의 기계를 끄면 $t$ 리터의 액체가 쏟아진다. 지진은 한 번만 일어나며 모든 홀에 같은 시각에 영향을 준다. 지진 전에는 기계를 끌 수 없다. 시작 홀은 아무 곳이나 고를 수 있다.

다음 그림은 첫 번째 예시의 광산 구조다.

입력

첫 줄에 홀의 개수를 나타내는 정수 $n$ 이 주어진다. 홀은 $1$ 부터 $n$ 까지 번호가 매겨져 있다. 이어서 $n-1$ 개의 줄에 공백으로 구분된 두 정수 $u$ 와 $v$ 가 주어지며, $1 \le u < v \le n$ 이다. 이는 홀 $u$ 와 홀 $v$ 를 잇는 터널이 있다는 뜻이다.

출력

쏟아지는 액체의 최소량을 리터 단위의 정수 하나로 출력한다.

제한

항상 $1 \le n \le 10^5$ 이다.

예제3

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