← 返回题目列表

Codeforces · 1863/I

I. 冗余路由

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

给你一棵树,其中 $$$n$$$ 个顶点标记为 $$$1, 2, \ldots, n$$$。树中简单路径的长度是其中的顶点数。

您要选择一组长度至少为 $$$2$$$ 的简单路径,但不能同时选择两个相互包含的不同路径。找出这样一个集合的最大可能大小。

正式来说,如果一个顶点集 $$$S$$$ 包含至少两个顶点并且与树中简单路径的顶点集一致,则该顶点集称为路径。不同路线的集合称为时间表。如果 T$$$ 中有一条不同的路线 $$$S' \in T$$$ 使得 $$$S \子集 S'$$$,则时间表 $$$T$$$ 中的路线 $$$S$$$ 被称为冗余路线。如果一个时间表不包含冗余路线,则该时间表被称为有效的。在有效的时间表中找到尽可能多的路线。

输入

第一行包含一个整数 $$$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$$$ 连接的顶点数边缘。

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

输出

打印一个整数——问题的答案。

示例

输入 #1

4
1 2
1 3
1 4

输出 #1

3

输入 #2

7
2 1
3 2
4 3
5 3
6 4
7 4

输出 #2

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\}\}$$$。