No.1484 Writing Numbers on a Tree / Just Write Numbers! 2
Problem Statement
There is a tree with $N$ vertices. The $i$-th edge connects vertex $A_i$ and vertex $B_i$. Consider writing integers between $1$ and $N$, inclusive, on the vertices of this tree, $1$ integer on each vertex, without duplicates.
The score of a way of writing is defined as $\displaystyle \sum_{i=1}^{N-1}\mathrm{dist}(i,i+1)$. Here, $\mathrm{dist}(x,y)$ is the distance between the vertex on which $x$ is written and the vertex on which $y$ is written.
Find the minimum possible score.
Input
$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_{N-1}\ B_{N-1}$
- All input values are integers.
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \lt B_i \le N$
- The given graph is a tree.
Output
Print the minimum possible score, followed by a newline.
Sample
Sample 1
Input
4 2 3 2 4 1 2
Output
4
For example, if you write on each vertex the integer equal to its vertex number, the score is $4$.
Sample 2
Input
5 1 2 2 3 3 4 4 5
Output
4
Sample 3
Input
18 5 17 5 13 2 5 8 13 2 4 5 6 3 17 8 15 6 18 12 13 2 10 2 11 2 16 1 17 7 11 4 9 13 14
Output
28
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
platinum