题目描述

「BalticOI 2023」Minequake

安装在摩拉维亚矮人废弃矿井中的全自动微型酿酒厂是矮人巧妙和精湛工艺的真实写照！可惜，有时地震会导致矿井震动，导致管道和漏斗错位，珍贵的液体洒落一地。作为酿酒厂的安全主管，你负责在地震发生时关闭每个大厅的机器。

在隧道中行走需要时间，因此你不可避免地会晚关许多机器。这种情况无法避免，但你要尽量减少溢出的液体总量。

矮人矿井由 $n$ 个大厅组成，大厅由 $n-1$ 条隧道连接。整个系统是连通的，因此可以从任何一个大厅到达其他任何一个大厅。穿过一条隧道需要 $1$ 单位时间。关闭一台机器和穿越一个大厅不需要时间。在每个大厅中，地震后 $t$ 时关闭机器会泄漏 $t$ 升液体。恰好有一次地震，地震同时影响所有大厅，并且在地震前不能关闭任何机器。你可以从任何一个大厅出发。

---

输入格式

第一行一个整数 $n$，表示大厅数。我们假设大厅按 $1, \ldots, n$ 编号。

接下来 $n-1$ 行，每行两个整数 $u, v$ 且满足 $1 \le u < v \le n$，表示大厅 $u$ 和 $v$ 之间有一条隧道连接。

---

输出格式

输出一个整数：表示最少溢出的液体量。

---

样例 1

输入

3
1 2
2 3

输出

3

解释
矿井结构如下：

如果你从大厅 $2$ 出发，然后按 $2, 1, 2, 3$ 的顺序经过这些大厅，这样你可以在时刻 $0$（在大厅 $2$），时刻 $1$（在大厅 $1$）和时刻 $3$（在大厅 $3$）关闭对应大厅中的机器。这样总共会浪费 $0 + 1 + 3 = 4$ 升液体。

如果你从大厅 $1$ 出发，并按 $1, 2, 3$ 的顺序经过这些大厅，总浪费的液体为 $0 + 1 + 2 = 3$ 升，这样更好。

---

样例 2

输入

4
1 2
1 3
1 4

输出

7

---

样例 3

输入

1

输出

0

---

数据范围与提示

对于所有数据，满足 $1 \le n \le 10^5$。

详细子任务附加限制及分值如下表：

子任务	附加限制	分值
1	没有大厅连有超过两条隧道	18
2	最多有一个大厅连有超过两条隧道	19
3	$n \le 10$	20
4	$n \le 1000$	21
5	无附加限制	22

---