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.
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)$$$. 
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.
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def MI1():
    return map(int1, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7
fibo = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418]
ftoi = {f: i for (i, f) in enumerate(fibo)}
n = II()
to = [[] for _ in range(n)]
for e in range(n - 1):
    (u, v) = MI1()
    to[u].append(v)
    to[v].append(u)
if n <= 3:
    print('YES')
    exit()
if n not in ftoi:
    print('NO')
    exit()
stack = [0]
sz = [-1] * n
par = [-1] * n
while stack:
    u = stack.pop()
    if sz[u] == -1:
        sz[u] = 1
        stack.append(u)
        for v in to[u]:
            if v == par[u]:
                continue
            par[v] = u
            stack.append(v)
    else:
        sz[par[u]] += sz[u]
fin = [False] * n

def dfs(r, s):
    i = ftoi[s]
    (s1, s2) = (fibo[i - 1], fibo[i - 2])
    stack = [r]
    while stack:
        u = stack.pop()
        for v in to[u]:
            if v == par[u]:
                continue
            if fin[v]:
                continue
            if sz[v] == s1 or sz[v] == s2:
                fin[v] = True
                return v
            stack.append(v)
    return -1

def ok():
    root = [(0, sz[0])]
    while root:
        (r, s) = root.pop()
        u = dfs(r, s)
        if u == -1:
            return False
        s1 = sz[u]
        if s1 > 3:
            root.append((u, s1))
        if s - s1 > 3:
            root.append((r, s - s1))
        while u != r:
            u = par[u]
            sz[u] -= s1
    return True
print('YES' if ok() else 'NO')
import io, os
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
fibnum = [1, 1]
fibloc = {1: 1}
for _ in range(25):
    num = fibnum[-2] + fibnum[-1]
    fibloc[num] = len(fibnum)
    fibnum.append(num)

def judge(children, root, subnum, tot, parent):
    if tot <= 3:
        return True
    loc = fibloc[tot]
    queue = deque([root])
    while queue:
        index = queue.popleft()
        for child in children[index]:
            if subnum[child] == fibnum[loc - 1] or subnum[child] == fibnum[loc - 2]:
                i = parent[child]
                while i >= 0:
                    subnum[i] -= subnum[child]
                    i = parent[i]
                parent[child] = -1
                children[index].remove(child)
                return judge(children, root, subnum, tot - subnum[child], parent) and judge(children, child, subnum, subnum[child], parent)
            queue.append(child)
    return False

def main(t):
    n = int(input())
    neigh = [[] for i in range(n)]
    for _ in range(n - 1):
        (u, v) = map(int, input().split())
        neigh[v - 1].append(u - 1)
        neigh[u - 1].append(v - 1)
    if n not in fibloc:
        print('NO')
        return
    seq = [0]
    parent = [-1] * n
    subnum = [0] * n
    for index in seq:
        seq += neigh[index]
        for nextindex in neigh[index]:
            parent[nextindex] = index
            neigh[nextindex].remove(index)
    children = neigh
    for index in seq[::-1]:
        subnum[index] = 1 + sum([subnum[child] for child in children[index]])
    ans = judge(children, 0, subnum, n, parent)
    if ans:
        print('YES')
    else:
        print('NO')
main(1)
import io
import os
from collections import deque

def solve(N, edges):
    fib = [1, 1]
    while fib[-1] < N:
        fib.append(fib[-2] + fib[-1])
    fibToIndex = {x: i for (i, x) in enumerate(fib)}
    if N not in fibToIndex:
        return 'NO'
    graph = [[] for i in range(N)]
    for (u, v) in edges:
        graph[u].append(v)
        graph[v].append(u)
    root = 0
    q = [root]
    parent = [-1] * N
    for u in q:
        q += graph[u]
        for v in graph[u]:
            parent[v] = u
            graph[v].remove(u)
    children = graph
    subTreeSize = [-1] * N
    for u in q[::-1]:
        subTreeSize[u] = 1 + sum((subTreeSize[v] for v in children[u]))

    def isFib(root, numNodes):
        if numNodes <= 3:
            return True
        i = fibToIndex[numNodes]
        F1 = fib[i - 1]
        F2 = fib[i - 2]
        q = deque([root])
        while q:
            u = q.popleft()
            count = subTreeSize[u]
            if count == F1 or count == F2:
                p = parent[u]
                parent[u] = -1
                children[p].remove(u)
                while parent[p] != -1:
                    subTreeSize[p] -= count
                    p = parent[p]
                return isFib(u, count) and isFib(p, numNodes - count)
            q += graph[u]
        return False
    if isFib(root, N):
        return 'YES'
    return 'NO'
DEBUG = False
if DEBUG:
    N = 196418
    edges = []
    for i in range(N - 1):
        edges.append((i, i + 1))
    ans = solve(N, edges)
    print(ans)
    exit()
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    TC = 1
    for tc in range(1, TC + 1):
        (N,) = [int(x) for x in input().split()]
        edges = [[int(x) - 1 for x in input().split()] for i in range(N - 1)]
        ans = solve(N, edges)
        print(ans)