题目内容

在宇宙中有 $n$ 个空间站，初始时空间站之间通过 $n-1$ 条双向航道连接，保证任意两个空间站可达，且不存在环。航道管理部门发现，若存在一个空间站 $w$，使得在初始航道中存在 $(u,w)$ 和 $(w,v)$，那么可以额外在 $u$ 与 $v$ 之间修建一条新航道。管理部门可以在这些候选新航道中任意选择若干条进行修建。

定义 $d(i,j)$ 为修建后网络中空间站 $i$ 到 $j$ 的最短路径长度（即经过的最少航道数）。管理部门希望最小化所有有序空间站对距离之和，即 $\sum_{i=1}^{n}\sum_{j=1}^{n} d(i,j)$。请你计算这个最小值。

约束：空间站数量 $n$ 满足 $2 \le n \le 2 \times 10^5$。初始航道信息为 $n-1$ 行，每行两个整数表示一条航道的两端点，编号均为 $1$ 到 $n$ 之间，保证输入是一棵树。

输入描述

第一行输入一个整数 $n$，表示空间站的数量。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示初始存在连接 $u$ 与 $v$ 的航道。