Broadcast Stations

The connections between cities form a tree $T$ with $n$ vertices, and each vertex is one city. The distance between two vertices is the number of edges on the unique path between them. Broadcast stations that send out the same information have to be built in some of the cities. A station of transmission power $p$ reaches every city at distance $p$ or less from it.

Assign a non-negative integer $p(v)$, called the broadcast power, to every vertex $v$ of the vertex set $V$ of $T$. The assignment has to satisfy the following condition: every vertex $u$ with $p(u) = 0$ is within distance $p(v)$ of some vertex $v$ with $p(v) > 0$. A vertex $v$ with $p(v) > 0$ is a broadcast station of transmission power $p(v)$, and a vertex $u$ with $p(u) = 0$ can hear the broadcast of $v$ if $u$ is within distance $p(v)$ of $v$.

Among the assignments that satisfy the condition, find the minimum value of $\sum_{v \in V} p(v)$.

Figure A.1 shows two assignments of broadcast powers. In (a) only vertex 6 has broadcast power 4 and every other vertex has 0. Every vertex of broadcast power 0 can then hear vertex 6. In (b) vertices 3 and 9 have broadcast powers 2 and 1. Every vertex of broadcast power 0 can hear vertex 3 or vertex 9, and this assignment makes the sum of the broadcast powers as small as possible.

Figure A.1: two assignments of broadcast powers, (a) above and (b) below.

The first line contains one integer $n$ ($1 \le n \le 5000$), the number of vertices of the tree $T$. The vertices are numbered from 1 to $n$. Each of the next $n-1$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$), an edge that joins vertex $a$ and vertex $b$.

Print one line with one integer, the smallest sum of broadcast powers over all assignments that satisfy the condition.