C. 氙的攻击——帮派网络

每次测试的时间限制：$3$ 秒
每次测试的内存限制：$512$ 兆字节

在 A.R.C. Markland-N 的另一层楼，年轻的程序员西蒙·“氙”·杰克逊早早完成了他的项目（一如既往地提前）。闲来无事，他决定化身传奇黑客 “X”，与网络世界中的帮派展开对抗。

他的目标是包含 $n$ 个小帮派的网络。
该网络恰好有 $n-1$ 条直接链路，每条链路连接两个帮派。链路分布方式保证：任意两个帮派之间都存在唯一一条由若干条链路构成的简单路径。

通过数据挖掘，氙发现帮派使用了一种交叉加密方式以避免被查获：
每条链路被分配一个 $0$ 到 $n-2$ 之间 的整数，所有整数互不相同，且每个整数恰好被分配给某一条链路。
如果入侵者试图访问加密数据，他们必须突破 $S$ 层密码防护，其中 $S$ 的定义如下：

$$S = \sum_{1 \le u < v \le n} \mathrm{mex}(u, v)$$

这里，$\mathrm{mex}(u, v)$ 表示：在从帮派 $u$ 到帮派 $v$ 的唯一简单路径上的所有链路中，没有出现的最小非负整数。

氙并不知道整数是如何分配到链路上的，但这并不成问题。他打算让他的 AI 实例尝试所有可能的分配方式，但在此之前，他需要知道 $S$ 可能的最大值，以便高效部署 AI。

现在氙要编写 AI 脚本，预计两小时内完成。在他回来之前，你能找出最大的可能 $S$ 吗？

---

输入格式
第一行包含一个整数 $n$（$2 \le n \le 3000$），表示帮派数量。
接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示帮派 $u_i$ 和 $v_i$ 之间有一条直接链路。
数据保证链路分布使得任意两个帮派之间都有唯一一条简单路径相连。

输出格式
输出最大的可能值 $S$ —— 帮派网络中的密码防护层数。

---

详细题解

第一步：公式转化

首先，将 $S$ 按 $\mathrm{mex}$ 值重新组织：

$$S = \sum_{1 \le u < v \le n} \mathrm{mex}(u,v) = \sum_{x=1}^{n} \left( \sum_{\mathrm{mex}(u,v) = x} x \right) $$

关键观察：对于固定的 $x$，满足 $\mathrm{mex}(u,v) \ge x$ 的 $(u,v)$ 对数记为 $f(x)$。那么：

$$\sum_{\mathrm{mex}(u,v) = x} x = \sum_{\mathrm{mex}(u,v) \ge x} 1 $$

因此：

$$S = \sum_{x=1}^{n} f(x)$$

其中：

$$f(x) = \#\{ (u,v) \mid 1 \le u < v \le n,\ \mathrm{mex}(u,v) \ge x \} $$

$\mathrm{mex}(u,v) \ge x$ 等价于：从 $u$ 到 $v$ 的路径上包含了 $0,1,\dots,x-1$ 这 $x$ 个整数。

---

第二步：放置数字的贪心策略

考虑按顺序将数字 $0,1,2,\dots,n-2$ 放到树的边上。
假设已经放置好了 $0,1,\dots,x-1$，现在要放数字 $x$。
为了最大化最终的 $S$，我们应该尽量让更多路径的 $\mathrm{mex}$ 变大。具体来说，如果能让某条路径包含 $0,1,\dots,x$，那么 $f(x+1)$ 就会增加，从而 $S$ 更大。

因此，最优策略是：尽量让 $0,1,\dots,l-1$ 连续出现在同一条简单路径上（其中 $l$ 是该路径的边数）。
剩下的数字 $l,l+1,\dots,n-2$ 可以任意放置，因为它们不会影响 $f(1),f(2),\dots,f(l)$ 的值。

结论：在最优解中，存在一条连接两个叶子节点的路径，包含了 $0,1,\dots,l-1$ 所有数字。

---

第三步：路径上的最优排列

设选定的路径 $P$ 有 $l$ 条边，按顺序记为 $e_1,e_2,\dots,e_l$。
可以证明：为了最大化贡献，数字 $0,1,\dots,l-1$ 在 $P$ 上的排列必须是谷形序列（valley sequence）：

存在某个位置 $p$，使得：

$$a_1 > a_2 > \dots > a_p < a_{p+1} < \dots < a_l$$

直观理解：数字 $0$ 放在路径的中间，然后 $1,2,\dots$ 依次向两端扩展。这样能最大化覆盖更多的节点对。

---

第四步：动态规划状态定义

设 $dp[u][v]$ 表示：假设数字 $0,1,\dots,l-1$ 已经填在 $u$ 到 $v$ 的路径上（路径长度为 $l$），并且排列是最优的，此时 $\sum_{x=1}^{l} f(x)$ 的最大值。

我们需要建立 $dp[u][v]$ 的递推关系。

---

第五步：辅助定义

对每个可能的根 $r$，预处理：

• $par(r,u)$：以 $r$ 为根时，节点 $u$ 的父节点。
• $sub(r,u)$：以 $r$ 为根时，节点 $u$ 的子树大小。

这些可以在 $O(n^2)$ 内完成：对每个 $r$ 做一次 DFS。

对于两个相邻节点 $u$ 和 $v$（在树上直接相连），定义：

• $sub(u,v)$：以 $u$ 为根时，$v$ 的子树大小。
  实际上，$sub(u,v)$ 等于：从树上去掉边 $(u,v)$ 后，$v$ 那一侧的节点数。

注意重要关系：$sub(u,v) + sub(v,u) = n$。

---

第六步：递推公式推导

假设当前路径是 $u \to v$，长度为 $l$，已经填好了 $0,\dots,l-1$，现在要放置数字 $l$。
数字 $l$ 只能放在路径的两端进行扩展，有两种选择：

情况1：将数字 $l$ 放在边 $(u, par(v,u))$ 上
即从 $v$ 向 $u$ 方向延伸一步，新路径为 $par(v,u) \to v$。
增加的贡献：所有包含 $0,\dots,l$ 的路径对 $(a,b)$ 的数量，等于新路径两端子树大小的乘积：$sub(u,v) \times sub(v,u)$。
再加上原来路径的贡献 $dp[par(v,u)][v]$。
因此总贡献为：$sub(u,v) \times sub(v,u) + dp[par(v,u)][v]$。

情况2：将数字 $l$ 放在边 $(v, par(u,v))$ 上
即从 $u$ 向 $v$ 方向延伸一步，新路径为 $u \to par(u,v)$。
同理，贡献为：$sub(u,v) \times sub(v,u) + dp[u][par(u,v)]$。

由于我们要最大化总贡献，取两种情况的最大值：

$$dp[u][v] = sub(u,v) \times sub(v,u) + \max\big(dp[par(v,u)][v],\ dp[u][par(u,v)]\big) $$

---

第七步：边界条件

• 当 $u = v$ 时，路径长度为 $0$，$dp[u][u] = 0$。
• 当 $u$ 和 $v$ 相邻时，$l = 1$，没有更小的 $dp$ 可参考，直接计算： $dp[u][v] = sub(u,v) \times sub(v,u)$。

---

第八步：计算顺序

由于递推式中 $par(v,u)$ 和 $par(u,v)$ 分别是从 $v$ 往 $u$ 和从 $u$ 往 $v$ 各走一步，路径长度在增加。
因此可以按照路径长度从小到大的顺序计算 $dp[u][v]$，或者使用记忆化搜索。

---

第九步：最终答案

最终答案是：

$$\max_{1 \le u < v \le n} dp[u][v]$$

因为我们总可以选择最优的那条路径来放置 $0,1,\dots,l-1$，而剩下的数字不影响 $S$ 的值（因为 $f(x) = 0$ 对 $x > l$ 成立）。

---

第十步：复杂度分析

• 预处理 $par$ 和 $sub$：$O(n^2)$（$n$ 次 DFS，每次 $O(n)$）。
• 计算 $dp[u][v]$：共有 $O(n^2)$ 个状态，每个状态 $O(1)$ 转移。
• 总时间复杂度：$O(n^2)$，对 $n \le 3000$ 可行。
• 空间复杂度：$O(n^2)$，存储 $par$、$sub$ 和 $dp$ 三个 $n \times n$ 数组。

---

总结

本题的核心思想：

1. 将 $S$ 转化为 $\sum_{x=1}^{n} f(x)$，其中 $f(x)$ 是路径包含 $0,\dots,x-1$ 的节点对数。
2. 最优解中 $0,\dots,l-1$ 在一条路径上，且排列成谷形。
3. 定义 $dp[u][v]$ 表示 $u$ 到 $v$ 路径上放置 $0,\dots,l-1$ 的最大 $\sum_{x=1}^{l} f(x)$。
4. 递推关系：新数字 $l$ 只能放在路径两端，贡献为两端子树大小乘积，加上原来的 $dp$ 值。
5. 预处理每个节点为根时的父节点和子树大小，$O(n^2)$ 完成。
6. 最终答案为所有点对 $dp[u][v]$ 的最大值。