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