Fib-tree
Contest: Codeforces Global Round 13
Difficulty rating: 2400
Tags: brute force, dfs and similar, divide and conquer, number theory, trees

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

Example input:
3
1 2
2 3

Example output:
YES

Example input:
5
1 2
1 3
1 4
1 5

Example output:
NO

Editorial:
Firstly, we can discover that we can only cut a tree in the size of $$$f_{i}$$$ into one in size of $$$f_{i-1}$$$ and one in size of $$$f_{i-2}$$$.
Proof:
We want to show that the only solution to $$$f_i=f_j+f_k$$$ is $$$(j,k)=(i-1,i-2)$$$ for $$$j \geq k$$$. Clearly, $$$i>j$$$, otherwise, $$$f_i<f_j+f_k$$$. Furthermore, $$$j>i-2$$$ as $$$f_i>2 \cdot f_{i-2}$$$. Therefore, we have shown the only solution is $$$(j,k)=(i-1,i-2)$$$.
However, we will have 2 ways to partition the tree sometimes. But it turns out we can cut any edge!
We will prove that if some edge cuts Fib-tree of $$$F_n$$$ vertices into trees with sizes $$$F_{n-1}$$$ and $$$F_{n-2}$$$, we can cut it, and the resulting trees are also Fib-trees.
Proof:
By induction. For $$$n = 2$$$ it's obvious.
If only edge cuts Fib-tree into trees with sizes $$$F_{n-1}$$$ and $$$F_{n-2}$$$, we have to cut it.
If there are two such edges: suppose that cutting the first edge results in making two Fib-trees. Then in the tree of size $$$F_{n-1}$$$ the second edge divides it into trees of sizes $$$F_{n-2}$$$ and $$$F_{n-3}$$$, so we can cut it as well in the next step. But then we could as well cut the second edge first: we will have one Fib-tree of size $$$F_{n-2}$$$, and one tree of size $$$F_{n-1}$$$ which is cut into Fib-trees of sizes $$$F_{n-2}$$$ and $$$F_{n-3}$$$ by the first edge, so it's also a Fib-tree! QED
Because the growth of Fibonacci sequence is approximately $$$O(\phi^n)$$$, we only need to cut our tree $$$O(\log_\phi n)$$$ times: every time, if we find the splitting edge, we cut it, and recurse to the resulting trees, if at some point there was no splitting edge — tree isn't Fib-tree.
Finally, we got an $$$O(n\log_\phi n)$$$ solution.