#P1491E. Fib-tree
-
ID: 5804
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Fib-tree
No submission language available for this problem.
Description
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.
Input
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
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.
Samples
3
1 2
2 3
YES
5
1 2
1 3
1 4
1 5
NO
5
1 3
1 2
4 5
3 4
YES
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)$.