← 返回题目列表

Codeforces · 718/D

D. 安德鲁和化学

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

在化学课上,安德鲁了解到饱和烃(烷烃)会发生自由基氯化反应。安德鲁是一个非常好奇的男孩,所以他想知道对于给定的烷烃可能有多少种不同的反应产物。他成功地解决了小分子的任务,但对于大分子,他遇到了一些困难,需要你的帮助。

正式地,给你一棵由 n 个顶点组成的树,每个顶点的度不超过 4。你必须计算通过向这棵树添加一个新顶点和一个新边可以获得的不同非同构树的数量,这样图仍然是树,并且每个顶点的度不超过 4。

如果存在双射 f(v),使得顶点 u 和 v 通过边连接当且仅当顶点 f(v) 和 f(u) 通过边连接时,两棵树是同构的。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) - 树中的顶点数。

然后接下来的 n - 1 行包含边缘描述。每条边由两个整数 ui 和 vi (1 ≤ ui, vi ≤ n) 给出——由边连接的顶点的索引。保证给定的图是一棵树,并且每个顶点的度数不超过4。

输出

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

示例

输入 #1

4
1 2
2 3
2 4

输出 #1

2

输入 #2

5
1 2
1 3
1 4
1 5

输出 #2

1

输入 #3

5
2 5
5 3
4 3
4 1

输出 #3

3

注意

在第一个示例中,可以向任何现有顶点添加新顶点,但是我们通过向顶点 1、3 和 4 添加新顶点获得的树是同构的,因此答案是 2。

在第二个示例中,无法向第一个顶点添加新顶点,因为其度数已等于 4。向顶点 2、3、4、5 添加新顶点得到的树是同构的,因此答案为 1。