CF1292C.Xenon's Attack on the Gangs

INSPION FullBand Master - INSPION

INSPION - IOLITE-SUNSTONE

On another floor of the A.R.C. Markland-N, the young man Simon "Xenon" Jackson, takes a break after finishing his project early (as always). Having a lot of free time, he decides to put on his legendary hacker "X" instinct and fight against the gangs of the cyber world.

His target is a network of $n$ small gangs. This network contains exactly $n - 1$ direct links, each of them connecting two gangs together. The links are placed in such a way that every pair of gangs is connected through a sequence of direct links.

By mining data, Xenon figured out that the gangs used a form of cross-encryption to avoid being busted: every link was assigned an integer from $0$ to $n - 2$ such that all assigned integers are distinct and every integer was assigned to some link. If an intruder tries to access the encrypted data, they will have to surpass $S$ password layers, with $S$ being defined by the following formula:

$$S = \\sum\_{1 \\leq u \\lt v \\leq n} mex(u, v)$$

Here, $mex(u, v)$ denotes the smallest non-negative integer that does not appear on any link on the unique simple path from gang $u$ to gang $v$.

Xenon doesn't know the way the integers are assigned, but it's not a problem. He decides to let his AI's instances try all the passwords on his behalf, but before that, he needs to know the maximum possible value of $S$, so that the AIs can be deployed efficiently.

Now, Xenon is out to write the AI scripts, and he is expected to finish them in two hours. Can you find the maximum possible $S$ before he returns?

INSPION FullBand 主控版 - INSPION

INSPION - IOLITE-SUNSTONE

在 A.R.C. Markland-N 的另一层楼中，青年西蒙·“氙”·杰克逊（Simon "Xenon" Jackson）提前完成了自己的项目（一如既往），于是稍作休息。由于空闲时间充裕，他决定启动自己传奇的黑客代号“X”的直觉，向网络世界的黑帮势力发起挑战。

他的目标是一个由 $n$ 个小型黑帮组成的网络。该网络恰好包含 $n - 1$ 条直接连接，每条连接将两个黑帮彼此相连。这些连接的布局方式使得任意两个黑帮之间都可通过若干条直接连接构成的路径互相连通（即整个网络是一棵树）。

通过数据挖掘，氙发现这些黑帮采用了一种交叉加密机制以逃避打击：每条连接被分配一个 $0$ 到 $n - 2$ 之间的整数，且所有分配的整数互不相同，即每个整数恰好被分配给某一条连接。

若入侵者试图访问加密数据，则必须突破 $S$ 层密码防护，其中 $S$ 由如下公式定义：

$$S = \sum\_{1 \leq u < v \leq n} mex(u, v)$$

此处，$mex(u, v)$ 表示从黑帮 $u$ 到黑帮 $v$ 的唯一简单路径上所有连接所分配的整数中未出现的最小非负整数（即该路径上边权集合的 mex 值）。

氙并不知道这些整数的具体分配方式，但这难不倒他。他决定让自己的多个 AI 实例替他尝试所有可能的密码；但在部署前，他需要先确定 $S$ 的最大可能值，以便高效地调度 AI。

此刻，氙正忙着编写 AI 脚本，预计两小时内完成。你能否在他返回之前，求出 $S$ 的最大可能值？

The first line contains an integer $n$ ($2 \leq n \leq 3000$), the number of gangs in the network.

Each of the next $n - 1$ lines contains integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$; $u_i \neq v_i$), indicating there's a direct link between gangs $u_i$ and $v_i$.

It's guaranteed that links are placed in such a way that each pair of gangs will be connected by exactly one simple path.

第一行包含一个整数 $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$ 与帮派 $v_i$ 之间存在一条直接连接。

保证这些连接的布置方式使得任意两个帮派之间都恰好存在唯一的一条简单路径。

Print the maximum possible value of $S$ — the number of password layers in the gangs' network.

输出 $S$ 的最大可能值——即帮派网络中密码层的数量。

In the first example, one can achieve the maximum $S$ with the following assignment:

With this assignment, $mex(1, 2) = 0$, $mex(1, 3) = 2$ and $mex(2, 3) = 1$. Therefore, $S = 0 + 2 + 1 = 3$.

In the second example, one can achieve the maximum $S$ with the following assignment:

With this assignment, all non-zero mex value are listed below:

• $mex(1, 3) = 1$
• $mex(1, 5) = 2$
• $mex(2, 3) = 1$
• $mex(2, 5) = 2$
• $mex(3, 4) = 1$
• $mex(4, 5) = 3$

Therefore, $S = 1 + 2 + 1 + 2 + 1 + 3 = 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$。