Redaksiya

Fact 1: for the resulting tree (with $n\le 10^{18}$), the height of the tree is at most 22.

Group 1: $n\le 100$.

It is possible to construct trees.

Now, in the query, we have 2 vertices and we need to find the distance between them. This is a standard problem for DFS or BFS.

Group 2: $n\le 10^6$.

It is possible to construct trees.

For each vertex, we will maintain its depth in the tree.

For each query, for each vertex, find the list of vertices above it. Find the deepest vertex that is in both lists (it always exists, as vertex 1 belongs to both lists). Let's call this vertex $X$.

The answer to the query will be the depth of vertex $u$ + the depth of vertex $v$ - 2 * (the depth of $X$).

The complexity of the solution is $O(n+q\ast d)$, where $d$ is the depth of the tree, and the memory is $n$.

Group 3: $n\le 10^{12}$.

Notice that at each depth, there will be vertices within a certain range from $l$ to $r$.

For each depth $i$, we will maintain 2 numbers $(l,r)$ such that the numbers of all vertices at depth $i$ are within the range $(l,r)$, and there are no vertices with other depths within the range $(l,r)$.

We will maintain this for the height. For height 1, this is the range $(1,1)$. Then, we iterate through all heights from 2 to 22 and recalculate the range.

If at height $i-1$ the range is $(l,r)$, then at height $i$ the range is $(r+1,r+1,count\_bits(l,r))$, where $count\_bits(l,r)$ is the total number of bits in the numbers from $l$ to $r$.

$count\_bits(l,r)$ can be calculated by iterating through all bits from 0 to 61 and finding the number of bits in the prefix $(0,r)$ and subtracting the number in the range $(0,l-1)$.

Next, we need to learn how to find the parent for a vertex. We can find its depth using binary search and an array of ranges. Then, we take the depth one less and, using binary search and the function $count\_bits(l,r)$, find the parent of the vertex.

The answer to the queries will be the same as in the second subgroup, but we will find the depth and parent of the vertex using the methods described above in the tutorial.

The complexity of the solution is $O(q\ast lo{g}^2\ast d)$, where $d$ is the depth of the tree.

Group 4: $n\le 10^{18}$.

Asymptotically, the solution remains the same, but we can simply reduce the constant.

For example, when calculating $count\_bits(l,r)$ in binary search to find the parent, we notice that there will be log queries with the same $l$, which means we can calculate the number of bits in the range $(0,l-1)$ once.