← 返回题目列表

Codeforces · 1252/F

F. 定期造林

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

植树造林是指种植一堆树木来培育森林的行为,通常是为了取代已被砍伐的森林。奇怪的是,图论学家对于如何创造森林还有另一种想法,即砍伐一棵树!

树是由 $$$N $$$ 个节点组成的图,这些节点通过 $$$N - 1$$$ 边连接。令 $$$u$$$ 为树 $$$U$$$ 中的一个节点,其度至少为 $$$2$$$ (即直接连接到 $$$U$$$ 中至少 $$$2$$$ 的其他节点)。如果我们从 $$$U$$$ 中删除 $$$u$$$,那么我们将得到两个或更多不相连的(较小的)树,或者也被图论学家称为森林。在这个问题中,我们将研究图论学家所做的特殊造林。

设 $$$V(S)$$$ 为树 $$$S$$$ 中的节点集,$$$V(T)$$$ 为树 $$$T$$$ 中的节点集。如果存在双射 $$$f : V(S) \rightarrow V(T)$$$ ,则树 $$$S$$$ 和树 $$$T$$$ 是相同的,这样对于 $$$V(S)$$$ 中的所有节点对 $$$(s_i, s_j)$$$、$$$s_i$$$ 和 $$$s_j$$$ 通过 $$$S$$$ 中的边连接当且仅当节点 $$$f(s_i)$$$ 和 $$$f(s_j)$$$ 通过 $$$T$$$ 中的边连接。请注意,$$$f(s) = t$$$ 意味着$$$S$$$ 中的节点$$$s$$$ 对应于$$$T$$$ 中的节点$$$t$$$。

当且仅当从 $$$U$$$ 中删除 $$$u$$$ 导致两个或多个断开的树,并且所有这些断开的树都是两两相同时,我们将 $$$U$$$ 树中的节点 $$$u$$$ 称为良好的切割点。

给定一棵树$$$U$$$,你的任务是确定$$$U$$$中是否存在好的切割点。如果存在这样的节点,那么你应该输出通过恰好删除一个好的切割点可以获得的最大断开树数。

例如,考虑以下 $$$13$$$ 节点树。

这棵树中正好有一个好的切点,即节点$$$4$$$。观察到,通过删除节点 $$$4$$$,我们将得到三棵相同的树(在本例中为折线图),即 $$$\{5, 1, 7, 13\}$$$、$$$\{8, 2, 11, 6\}$$$ 和 $$$\{3, 12, 9, 10\}$$$,它们用 $$$A$$$ 表示,图中分别为$$$B$$$ 和$$$C$$$。

- $$$A$$$ 和 $$$B$$$ 之间的双射函数:$$$f(5) = 8$$$、$$$f(1) = 2$$$、$$$f(7) = 11$$$ 和 $$$f(13) = 6$$$。
- $$$A$$$ 和 $$$C$$$ 之间的双射函数:$$$f(5) = 3$$$、$$$f(1) = 12$$$、$$$f(7) = 9$$$ 和 $$$f(13) = 10$$$。
- $$$B$$$ 和 $$$C$$$ 之间的双射函数:$$$f(8) = 3$$$、$$$f(2) = 12$$$、$$$f(11) = 9$$$ 和 $$$f(6) = 10$$$。

输入

输入以包含整数的行开头: $$$N$$$ ($$$3 \le N \le 4000$$$) 表示给定树中的节点数。接下来的 $$$N - 1$$$ 行每行包含两个整数: $$$a_i$$$ $$$b_i$$$ ($$$1 \le a_i < b_i \le N$$$) 表示给定树中的边 $$$(a_i,b_i)$$$。保证给定树中的任意两个节点通过边序列相互连接。

输出

在一行中输出一个整数,表示通过恰好删除一个好切割点可以获得的断开树的最大数量,如果没有这样的好切割点,则输出-1。

示例

输入 #1

13
1 5
1 7
2 4
2 8
2 11
3 12
4 7
4 12
6 11
7 13
9 10
9 12

输出 #1

3

输入 #2

6
1 2
1 3
2 4
3 5
3 6

输出 #2

-1

注意

示例输入/输出#1 的说明

这是问题描述中的示例。