题解

题面描述

题目给出一棵含有 $n$ 个结点的树，根节点为 $1$。每个结点的权值定义为该结点到结点 $1$ 的边数。现在允许操作：选择一个非 $1$ 号结点，将以该结点为根的子树重新挂接到结点 $1$ 下。要求求出经过一次该操作后整棵树权值之和的最小值。

思路

题目内容

小红拿到一棵树，结点总数为$n$，根节点为$1$

定义每个点的权值为到结点$1$的边数。

现在小红可以选择一个非1号结点，使得以该结点为根节点的子树成为$1$号结点的子结点。

求整棵树的最小权值之和是多少?

输入描述

第一行一个整数$n(1≤n≤2×10^5)$,表示树的结点总数。

接下来$n-1$行，每行两个整数$u,v(1 ≤u,v≤n)$,表示$u$和$v$之间有一条边。

输出描述

一个整数，表示整棵树的最小权值之和。

样例1

输入

5
1 2
2 3
3 4
4 5

输出

6