CF1863I.Redundant Routes

You are given a tree with $n$ vertices labeled $1, 2, \ldots, n$. The length of a simple path in the tree is the number of vertices in it.

You are to select a set of simple paths of length at least $2$ each, but you cannot simultaneously select two distinct paths contained one in another. Find the largest possible size of such a set.

Formally, a set $S$ of vertices is called a route if it contains at least two vertices and coincides with the set of vertices of a simple path in the tree. A collection of distinct routes is called a timetable. A route $S$ in a timetable $T$ is called redundant if there is a different route $S' \in T$ such that $S \subset S'$. A timetable is called efficient if it contains no redundant routes. Find the largest possible number of routes in an efficient timetable.

给你一棵包含 $n$ 个顶点的树，顶点编号为 $1, 2, \ldots, n$。树中一条简单路径的长度定义为该路径所含顶点的个数。

你需要选出一组简单路径，每条路径的长度至少为 $2$；但不允许同时选择两条满足“其中一条完全包含于另一条”的不同路径。求这种路径集合的最大可能大小。

形式化地，若一个顶点集合 $S$ 至少包含两个顶点，且恰好等于树中某条简单路径上的所有顶点，则称 $S$ 为一条路线（route）。若干互不相同的路线构成的集合称为一个时刻表（timetable）。在时刻表 $T$ 中，若某条路线 $S \in T$ 满足：存在另一条不同的路线 $S' \in T$，使得 $S \subset S'$，则称 $S$ 是冗余的（redundant）。若一个时刻表不包含任何冗余路线，则称其为高效的（efficient）。求一个高效时刻表中所能包含的路线的最大数目。

The first line contains a single integer $n$ ($2 \le n \le 3000$).

The $i$-th of the following $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$) — the numbers of vertices connected by the $i$-th edge.

It is guaranteed that the given edges form a tree.

第一行包含一个整数 $n$（$2 \le n \le 3000$）。

接下来的 $n - 1$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，且 $u_i \neq v_i$），表示第 $i$ 条边所连接的两个顶点的编号。

保证给定的边构成一棵树。

Print a single integer — the answer to the problem.

输出一个整数——该问题的答案。

In the first example, possible efficient timetables are ${{1, 2}, {1, 3}, {1, 4}}$ and ${{1, 2, 3}, {1, 2, 4}, {1, 3, 4}}$.

In the second example, we can choose ${ {1, 2, 3}, {2, 3, 4}, {3, 4, 6}, {2, 3, 5}, {3, 4, 5}, {3, 4, 7}, {4, 6, 7}}$.

在第一个例子中，可能的高效时间表为 $\{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\}$。