Date

Yudam and Woohyun are dating. Worried that Woohyun may be unfaithful, Yudam wants to monitor the places they often visit with CCTV cameras.

The connections between the places form a tree with $N$ vertices and $N-1$ edges. The distance between two vertices $u$ and $v$ is the number of edges on the unique simple path joining them.

Choose a nonnegative integer $B_v$ for every vertex $v$.

• If $B_v=0$, no CCTV camera is installed at vertex $v$.
• If $B_v\geq 1$, a CCTV camera of range $B_v$ is installed at vertex $v$. Its cost is $B_v$, and it monitors every vertex whose distance from $v$ is at most $B_v$.

Find the minimum possible total cost $\sum_{v=1}^{N} B_v$ such that every vertex is monitored by at least one CCTV camera.

The input is given from Standard Input in the following format:

$N$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_{N-1}\ v_{N-1}$

For each $i$ ($1\leq i\leq N-1$), there is an edge joining vertices $u_i$ and $v_i$.

Print the minimum total cost required to monitor every vertex.

• $2\leq N\leq 500\,000$.
• $1\leq u_i,v_i\leq N$ ($1\leq i\leq N-1$).
• $u_i\neq v_i$ ($1\leq i\leq N-1$).
• The given edges form a tree.