CF1491E.Fib-tree

Let $F_k$ denote the $k$-th term of Fibonacci sequence, defined as below:

• $F_0 = F_1 = 1$
• for any integer $n \geq 0$, $F_{n+2} = F_{n+1} + F_n$

You are given a tree with $n$ vertices. Recall that a tree is a connected undirected graph without cycles.

We call a tree a Fib-tree, if its number of vertices equals $F_k$ for some $k$, and at least one of the following conditions holds:

• The tree consists of only $1$ vertex;
• You can divide it into two Fib-trees by removing some edge of the tree.

Determine whether the given tree is a Fib-tree or not.

设 $F_k$ 表示斐波那契数列的第 $k$ 项，其定义如下：

• $F_0 = F_1 = 1$
• 对任意整数 $n \geq 0$，有 $F_{n+2} = F_{n+1} + F_n$

给定一棵包含 $n$ 个顶点的树。回忆一下，树是一种无环的连通无向图。

若一棵树满足以下条件，则称其为斐波那契树（Fib-tree）：

• 其顶点数等于某个 $k$ 对应的 $F_k$；
• 并且满足以下至少一个条件：
  • 该树仅含 $1$ 个顶点；
  • 存在某条边，将其删除后可将原树划分为两棵斐波那契树。

请判断给定的树是否为斐波那契树。

The first line of the input contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of vertices in the tree.

Then $n-1$ lines follow, each of which contains two integers $u$ and $v$ ($1\leq u,v \leq n$, $u \neq v$), representing an edge between vertices $u$ and $v$. It's guaranteed that given edges form a tree.

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

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

Print "YES" if the given tree is a Fib-tree, or "NO" otherwise.

You can print your answer in any case. For example, if the answer is "YES", then the output "Yes" or "yeS" will also be considered as correct answer.

如果给定的树是一棵 Fib-树，则输出 “YES”，否则输出 “NO”。

您可以以任意大小写形式输出答案。例如，若正确答案是 “YES”，则输出 “Yes” 或 “yeS” 也被视为正确答案。

In the first sample, we can cut the edge $(1, 2)$, and the tree will be split into $2$ trees of sizes $1$ and $2$ correspondently. Any tree of size $2$ is a Fib-tree, as it can be split into $2$ trees of size $1$.

In the second sample, no matter what edge we cut, the tree will be split into $2$ trees of sizes $1$ and $4$. As $4$ isn't $F_k$ for any $k$, it's not Fib-tree.

In the third sample, here is one possible order of cutting the edges so that all the trees in the process are Fib-trees: $(1, 3), (1, 2), (4, 5), (3, 4)$.

在第一个样例中，我们可以切断边 $(1, 2)$，此时树将被分割为两棵大小分别为 $1$ 和 $2$ 的子树。任何大小为 $2$ 的树都是 Fib-树，因为它可以进一步被分割为两棵大小均为 $1$ 的子树。

在第二个样例中，无论切断哪条边，树都将被分割为两棵大小分别为 $1$ 和 $4$ 的子树。由于 $4$ 不是任意 $k$ 对应的斐波那契数 $F_k$，因此它不是 Fib-树。

在第三个样例中，以下是一种可行的删边顺序，使得过程中出现的所有树均为 Fib-树：$(1, 3),\ (1, 2),\ (4, 5),\ (3, 4)$。