The simplest solution is to construct an entire graph in memory and for each query run a DFS traversal of the tree that will calculate the distance between two given nodes. A DFS traversal will correctly calculate the shortest path because the given graph is a tree, which means this path is the only path between these two nodes. The complexity of this solution is ~\mathcal O(QN)~.

A better solution also constructs the graph in memory, but before answering the queries it calculates the table of the lowest common ancestor. Using this data we can easily calculate the distance between two given nodes:

$$\displaystyle \begin{align*} &\mathrel{\phantom=} depth(x)-depth(lca(x, y))+depth(y)-depth(lca(x, y)) \\ &= (depth(x)+depth(y))-2 \times depth(lca(x, y)) \end{align*}$$

The complexity of this solution is ~\mathcal O(Q \log_K N)~.

For the maximal possible ~N~ from the task, the previous solution wouldn't work because of the too big space complexity: the table of the lowest common ancestor is too large. But, given the regular structure of the tree, we don't need to store the table of the lowest common ancestor in memory, because that information can be calculated on the spot. Let us enumerate the nodes from ~0~. Then the ~i^\text{th}~ child of node ~x~ can be calculated using the formula:

$$\displaystyle x \times K + 1 + i, i \in [0, K-1]$$

and the father of node ~x~:

$$\displaystyle \left\lfloor \frac{x-1}{K} \right\rfloor$$

where ~K~ is the order of the tree. These formulas enable us to efficiently calculate the lowest common ancestor using binary search. The time complexity of this solution is ~\mathcal O(Q \log_K^2 N)~, whereas the space complexity is constant.

There is a somewhat simpler solution with complexity ~\mathcal O(Q \log_K N)~ that does not use binary search.