CF1863I Redundant Routes

给定一棵有 $n$ 个顶点的树，顶点编号为 $1, 2, \ldots, n$。树中一条简单路径的长度定义为路径上顶点的数量。 你需要选择若干条长度至少为 $2$ 的简单路径，但不能同时选择两条互为包含关系的不同路径。请你求出这样的路径集合的最大可能大小。 形式化地说，若一个顶点集合 $S$ 至少包含两个顶点，且恰好是树中一条简单路径上的所有顶点，则称 $S$ 为一条“路线”。若若干条不同的路线组成一个集合，则称为“时间表”。如果时间表 $T$ 中存在一条路线 $S$，使得存在另一条不同的路线 $S' \in T$ 满足 $S \subset S'$，则称 $S$ 是“冗余”的。若时间表中没有冗余路线，则称其为“高效”的。请你求出高效时间表中路线数量的最大值。

第一行包含一个整数 $n$（$2 \le n \le 3000$）。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。 保证输入的边构成一棵树。

输出一个整数，表示高效时间表中路线数量的最大值。

在第一个样例中，可能的高效时间表有 $\{\{1, 2\}, \{1, 3\}, \{1, 4\}\}$ 和 $\{\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}\}$。 在第二个样例中，可以选择 $\{\{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 6\}, \{2, 3, 5\}, \{3, 4, 5\}, \{3, 4, 7\}, \{4, 6, 7\}\}$。 由 ChatGPT 4.1 翻译