Directions inside a Fibonacci tree

A Fibonacci tree T(k) is a binary tree built by a recurrence:

• T(0) and T(1) are a single node.
• For k >= 2, T(k) is a root whose left subtree is T(k - 2) and whose right subtree is T(k - 1).

Nodes are numbered 0, 1, 2, … in pre-order (root, then the whole left subtree, then the whole right subtree). For example T(3):

        0
       / \
      1   2          node 1 is T(1); node 2 is the root of T(2)
         / \
        3   4        node 3 is T(0); node 4 is T(1)

Write find_path(k: int, start: int, dest: int) -> str returning the shortest route from node start to node dest as a string of moves:

• 'U' moves to the parent, 'L' to the left child, 'R' to the right child.
• The shortest route goes up from start to the lowest common ancestor, then down to dest, so it is always some 'U's followed by some 'L'/'R's. Return "" when start == dest.

find_path(3, 3, 1)   # "UUL"
find_path(3, 4, 3)   # "UL"
find_path(3, 0, 4)   # "RR"
find_path(4, 8, 8)   # ""

Constraints: 0 <= k <= 85, and start, dest are valid node numbers of T(k). T(85) has more than 10**17 nodes, so you cannot build the tree; answer each query in about O(k) time.