CF1491E Fib-tree

设 $F_k$ 表示斐波那契数列的第 $k$ 项，定义如下： - $F_0 = F_1 = 1$； - 对于任意整数 $n \geq 0$，有 $F_{n+2} = F_{n+1} + F_n$。 给定一棵有 $n$ 个顶点的树。树是一个无环连通无向图。 我们称一棵树为 Fib-tree，当且仅当它的顶点数等于某个 $F_k$，并且至少满足以下条件之一： - 这棵树只包含 $1$ 个顶点； - 可以通过删除某条边，将其分成两棵 Fib-tree。 判断给定的树是否为 Fib-tree。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示树的顶点数。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），表示树中的一条边。保证给定的边构成一棵树。

如果给定的树是 Fib-tree，输出 "YES"；否则输出 "NO"。 你可以以任意大小写输出答案。例如，如果答案是 "YES"，则输出 "Yes" 或 "yeS" 也会被认为是正确答案。

在第一个样例中，可以切断边 $(1, 2)$，树会被分成大小分别为 $1$ 和 $2$ 的两棵树。任意大小为 $2$ 的树都是 Fib-tree，因为它可以被分成两个大小为 $1$ 的树。 在第二个样例中，无论切断哪条边，树都会被分成大小为 $1$ 和 $4$ 的两棵树。由于 $4$ 不是任何 $F_k$，因此它不是 Fib-tree。 在第三个样例中，存在一种切边顺序，使得过程中所有的树都是 Fib-tree，例如：$(1, 3), (1, 2), (4, 5), (3, 4)$。 由 ChatGPT 4.1 翻译