방송국 세우기

도시 사이의 연결 관계는 정점이 $n$개인 트리 $T$이고, 정점 하나가 도시 하나를 나타낸다. 두 정점 사이의 거리는 두 정점을 잇는 유일한 경로에 들어 있는 간선의 개수다. 같은 정보를 내보내는 방송국을 몇몇 도시에 세우려고 한다. 송신 출력이 $p$인 방송국은 자기 자신으로부터 거리가 $p$ 이하인 모든 도시에 방송을 보낸다.

$T$의 정점 집합 $V$에 속한 정점 $v$마다 음이 아닌 정수 $p(v)$를 배정한다. 이 값을 방송 출력이라고 부르며, 배정은 다음 조건을 만족해야 한다. $p(u) = 0$인 정점 $u$는 모두 $p(v) > 0$인 어떤 정점 $v$로부터 거리 $p(v)$ 이내에 있다. $p(v) > 0$인 정점 $v$는 송신 출력이 $p(v)$인 방송국이고, $p(u) = 0$인 정점 $u$는 $v$로부터 거리가 $p(v)$ 이하이면 $v$의 방송을 들을 수 있다.

조건을 만족하는 배정 가운데 $\sum_{v \in V} p(v)$를 최소로 하는 값을 구하라.

그림 A.1은 방송 출력을 배정한 두 가지 예다. (a)에서는 정점 6만 방송 출력이 4이고 나머지 정점은 모두 0이다. 이때 방송 출력이 0인 정점은 모두 정점 6의 방송을 들을 수 있다. (b)에서는 정점 3과 정점 9의 방송 출력이 각각 2와 1이다. 방송 출력이 0인 정점은 모두 정점 3이나 정점 9의 방송을 들을 수 있고, 이 배정이 방송 출력의 합을 가장 작게 만든다.

그림 A.1: 방송 출력을 배정한 두 가지 예. 위가 (a), 아래가 (b)다.

첫 줄에 트리 $T$의 정점 개수 $n$ ($1 \le n \le 5000$)이 주어진다. 정점 번호는 1번부터 $n$번까지다. 다음 $n-1$개 줄에는 각각 두 정수 $a$와 $b$ ($1 \le a, b \le n$)가 주어지며, 정점 $a$와 정점 $b$를 잇는 간선을 뜻한다.

방송 출력의 합이 가장 작은 배정에서 그 합을 한 줄에 출력한다.