Fib-tree (Codeforces 1491E)
Tags: Others, divide and conquer

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

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

Sample Inputs:
3
1 2
2 3

5
1 2
1 3
1 4
1 5

5
1 3
1 2
4 5
3 4

Sample Outputs:
YES

NO

YES

Solution (Python):
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')

Solution (Python):
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)

Solution (Python):
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)