問題一覧 > 通常問題

No.1484 Writing Numbers on a Tree / Just Write Numbers! 2

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 43
作問者 : first_vil / テスター : platinum
お気に入りにしたユーザー ProblemId : 6265 / 自分の提出
問題文最終更新日: 2021-04-19 01:00:19
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

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もしくは右上の雲マークをクリックしてアカウントを作成してください。