Clean Arrangements

문제

In graph drawing, a linear arrangement of a rooted (connected) tree $T=(V,E)T\; =\; (V,\; E)$ of $nn$ vertices is a planar drawing where $nn$ vertices of the tree are placed on a horizontal line, say the $xx$-axis, and (n − 1) edges are drawn as semicircular arcs above the line connecting their end vertices as shown in Figure 1. Such linear arrangement π maps each vertex to a distinct integer from $11$ to $nn$, representing its coordinate along the $xx$-axis.

Figure 1. (Left) A rooted tree $TT$ of nine vertices with the vertex $11$ as a root.

(Middle) A clean arrangement of $TT$.

(Right) An unclean arrangement of $TT$ because of the red edge $(3,7)(3,\; 7)$ covering the root.

In a linear arrangement π, the distance $d(u,v)d(u,\; v)$ between two vertices $uu$ and $vv$ is defined as the difference of their $xx$-coordinates, i.e., d(u, v) = |π(u) − π(v)|. Formally, for a rooted tree $T=(V,E)T\; =\; (V,\; E)$, the cost of a linear arrangement π of $TT$ is defined as ${\sum }_{(u,v)\in E}d(u,v)\backslash sum\_\{(u,v)\; \backslash in\; E\}\; \{d(u,v)\}$.

A clean arrangement π of a rooted tree $TT$ is a special linear arrangement π satisfying both conditions:

1. π has no edge crossings except at common end vertices of edges.
2. No edge covers the root vertex $rr$ of $TT$, that is, there is no edge $(u,v)(u,\; v)$ such that &pi;(u) < &pi;(r) < &pi;(v).

For example, the middle in Figure 1 is a clean arrangement of $TT$ in the left, but the right is not clean because the edge $(3,7)(3,\; 7)$ covers the root vertex $11$. The cost of the clean arrangement in the middle is $1111$, where there are three edges of distance two and five edges of distance one. This cost is the minimum among all clean arrangements of $TT$.

Given a rooted tree with the vertex $11$ as a root, write a program to output the minimum possible cost of clean arrangements of the tree.

입력

Your program is to read from standard input. The input starts with a line containing $nn$ (2 &le; n &le; 5\,000), where $nn$ is the number of vertices of the rooted tree. The vertices are numbered from $11$ to $nn$, and the root vertex is $11$. In the following (n &minus; 1) lines, each line contains two positive integers $uu$ and $vv$ which are end vertices of an (undirected) edge $(u,v)(u,\; v)$ of the tree, where $uu$ and $vv$ are distinct integers between $11$ and $nn$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the minimum cost of clean arrangements of the tree with root vertex $11$.

4
1 2
3 2
2 4

4

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

11