Let f(u, v, k) denote the distance of node u and v in F_k. From now on, we assume u ≤ v for convenience.

Let L denote the number of leaves of F₀.

If L = 1, the answer is just v - u since the tree is a path. Thus, we assume L > 1.

Note that the size of F_k is .

Note that the tree F_k can be constructed by replacing each leaf of F₀ with a copy of F_k - 1. (note that this is slightly different from the original defintion but you can prove that they're equivalent)

Thus, each node in the original tree corresponds to a range of nodes in F_k. Specifically, each non-leaf node in the original tree will correspond to one node in the final tree and each leaf node will correspond to S(F_k - 1) nodes in the final tree, where S(F_k - 1) is the size of F_k - 1, which can be computed with the formula above.

The main idea to calculate f(u, v, k) is to first check which node in F₀ contains u and v then try to recurse downwards.

Now, if k = 0 we can compute the answer directly from the original tree (note that you need to precompute heights and LCA to answer this in ).

Let's first consider the naive solution.

Iterate through the nodes of F₀ one by one in depth-first manner to determine which node u and v corresponds to. Let u' and v' be these nodes. Then, there are a few cases :

• If u and v corresponds to non-leaf nodes, return dist(u, v) and we're done.

• If u corresponds to a leaf node and v doesn't, then return dist(u', v') + f(0, u - S, k - 1), where S denotes the number of nodes in F_k encountered before we reach the node containing u. Similarly, we can do a similar recursion if v corresponds to a leaf and u doesn't.

• If u and v both corresponds to leaf node, then if u' = v', return f(u - S_u, v - S_v, k - 1) (S_u is number of nodes in F_k encountered before reaching u and S_v is similar) and if u' ≠ v', return dist(u', v') + f(0, u - S_u, k - 1) + f(0, v - S_v, k - 1).

This solution should work in O(kn) time (we omit the time required to calculate size of F_k for simplicity), which is clearly too slow.

The first optimization that can be made is to speed up the process of finding u', v' and S_u, S_v. Let's do a dfs on the tree and for each node u, store a pair (x, c), where x is the number of nodes encountered till now and c is the number of leaves encountered till now. Then, the total number of nodes in F_k encountered up to u is x + c·(S(F_k - 1) - 1).

With this, we can do a binary search and determine which nodes u and v correspond to in F₀ in time. However, the complexity is still , which is unacceptable.

The next optimization is to note that if k is large, for example when k > 32, the value of S(F_k) will definitely exceed 2³⁰. Thus, a lot of calculations can be omitted. Indeed, when we reach the case where u' = v', and let S denote the number of nodes in F₀ encountered before u', then we'll keep calling the functions f(u, v, k), f(u - S, v - S, k - 1), f(u - 2S, v - 2S, k - 2), ... until k ≤ 32 or one of the arguments become less than S. We can calculate exactly when this happen with some math and from there we can switch to the case f(0, v, k).

For f(0, v, k), the process is similar, except the answer will be increased by H, the height of v' in F₀ each time you recurse down, so you need to add a multiple of height of v' to the answer.

Thus, each query can be answered in time, and the total complexity is .