Fib-tree

题意翻译

定义 $F_k$ 为斐波那契数列的第 $k$ 项，也就是： * $F_0 = F_1 = 1$ * 对于任意 $n \ge 0$, $F_{n + 2} = F_{n + 1} + F_n$ 现在给你一棵包含了 $n$ 个结点的树。我们称一棵树为 Fib-tree，要求其结点数为某一个 $F_k$，且满足以下至少一个： * 树仅包含一个结点。 * 从某条边划开，形成的两棵子树都是 Fib-tree。 请判断给出的树是不是 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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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) $ .

题意翻译

定义 $F_k$ 为斐波那契数列的第 $k$ 项，也就是： * $F_0 = F_1 = 1$ * 对于任意 $n \ge 0$, $F_{n + 2} = F_{n + 1} + F_n$ 现在给你一棵包含了 $n$ 个结点的树。我们称一棵树为 Fib-tree，要求其结点数为某一个 $F_k$，且满足以下至少一个： * 树仅包含一个结点。 * 从某条边划开，形成的两棵子树都是 Fib-tree。 请判断给出的树是不是 Fib-tree。