← 返回题目列表

Codeforces · 1491/E

E. 纤维树

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

设 $$$F_k$$$ 表示斐波那契数列的第 $$$k$$$ 项,定义如下:

- $$$F_0 = F_1 = 1$$$
- 对于任何整数 $$$n \geq 0$$$, $$$F_{n+2} = F_{n+1} + F_n$$$

给你一棵有 $$$n$$$ 个顶点的树。回想一下,树是一个没有循环的连通无向图。

如果一棵树的顶点数等于 $$$F_k$$$ 对于某些 $$$k$$$,并且至少满足以下条件之一,则我们将树称为斐波那契树:

- 树仅由 $$$1$$$ 顶点组成;
- 您可以通过删除树的某些边缘将其分成两棵 Fib 树。

确定给定的树是否是 Fib 树。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 树中的顶点数。

接下来是 $$$n-1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\leq u,v \leq n$$$, $$$u \neq v$$$),表示顶点 $$$u$$$ 和 $$$v$$$ 之间的一条边。保证给定的边形成一棵树。

输出

如果给定的树是 Fib 树,则打印“YES”,否则打印“NO”。

在任何情况下您都可以打印您的答案。例如,如果答案为“YES”,则输出“Yes”或“yeS”也将被视为正确答案。

示例

输入 #1

3
1 2
2 3

输出 #1

YES

输入 #2

5
1 2
1 3
1 4
1 5

输出 #2

NO

输入 #3

5
1 3
1 2
4 5
3 4

输出 #3

YES

注意

在第一个示例中,我们可以切割边 $$$(1, 2)$$$,树将被分成相应大小为 $$$1$$$ 和 $$$2$$$ 的 $$$2$$$ 树。任何大小为 $$$2$$$ 的树都是 Fib 树,因为它可以分为大小为 $$$1$$$ 的 $$$2$$$ 树。

在第二个示例中,无论我们切割哪条边,树都会被分成 $$$2$$$ 大小为 $$$1$$$ 和 $$$4$$$ 的树。由于对于任何 $$$k$$$,$$$4$$$ 都不是 $$$F_k$$$,因此它不是斐波那契树。

在第三个示例中,以下是切割边缘的一种可能顺序,以便该过程中的所有树都是斐波那契树:$$$(1, 3), (1, 2), (4, 5), (3, 4)$$$。