← 返回题目列表

Codeforces · 1292/C

C. 塞农对帮派的攻击

中文机器翻译题面 查看原题

在 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$$$。