在 A.R.C. 的另一层马克兰-N,年轻的西蒙·“塞农”·杰克逊,在提前完成他的项目后休息了一下(一如既往)。拥有大量的空闲时间,他决定发挥他传奇的黑客“X”本能,与网络世界的黑帮作斗争。
他的目标是一个由 $$$n$$$ 小团伙组成的网络。该网络恰好包含 $$$n - 1$$$ 直接链接,每个链接都将两个帮派连接在一起。这些链接的放置方式使得每对帮派都通过一系列直接链接进行连接。
通过挖掘数据,Xenon 发现该团伙使用了一种交叉加密的形式来避免被破解:每个链接都被分配了一个从 $$$0$$$ 到 $$$n - 2$$$ 的整数,这样所有分配的整数都是不同的,并且每个整数都被分配给某个链接。如果入侵者试图访问加密数据,他们将必须超越 $$$S$$$ 密码层,$$$S$$$ 由以下公式定义:
$$$$$$S = \sum_{1 \leq u < v \leq n} mex(u, v)$$$$$$
这里,$$$mex(u, v)$$$表示在从组$$$u$$$到组$$$v$$$的唯一简单路径上的任何链接上都没有出现的最小非负整数。
Xenon 不知道整数的分配方式,但这不是问题。他决定让他的 AI 实例代表他尝试所有密码,但在此之前,他需要知道 $$$S$$$ 的最大可能值,以便可以有效地部署 AI。
现在,Xenon 正在编写 AI 脚本,预计他将在两个小时内完成。你能在他回来之前找到最大可能的$$$S$$$吗?
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 3000$$$),即网络中帮派的数量。
接下来的 $$$n - 1$$$ 行均包含整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$; $$$u_i \neq v_i$$$),表明帮派 $$$u_i$$$ 和 $$$u_i$$$ 之间有直接联系$$$v_i$$$。
保证链接的放置方式使得每对帮派将通过一条简单路径连接。
输出
打印 $$$S$$$ 的最大可能值 — 帮派网络中的密码层数。
示例
输入 #1
3 1 2 2 3
输出 #1
3
输入 #2
5 1 2 1 3 1 4 3 5
输出 #2
10
注意
在第一个示例中,可以通过以下赋值实现最大值 $$$S$$$:
通过此分配,$$$mex(1, 2) = 0$$$、$$$mex(1, 3) = 2$$$ 和 $$$mex(2, 3) = 1$$$。因此,$$$S = 0 + 2 + 1 = 3$$$。
在第二个示例中,可以通过以下分配实现最大值 $$$S$$$:
通过此分配,所有非零 mex 值列出如下:
- $$$mex(1, 3) = 1$$$
- $$$mex(1, 5) = 2$$$
- $$$mex(2, 3) = 1$$$
- $$$mex(2, 5) = 2$$$
- $$$mex(3, 4) = 1$$$
- $$$mex(4, 5) = 3$$$
因此,$$$S = 1 + 2 + 1 + 2 + 1 + 3 = 10$$$。