Here is a method to find the depth of every node in

$ operations.

Root the tree at

$, and let

$.

Take a power of two

$ such that

$. Since the depth of any node in the tree is less than

$, initially we can assume that the depth of every non-root node lies in

$.

Then we keep binary-splitting this interval.

Suppose that currently every node belongs to a depth segment of length

$. For a node

$, let

$ be the index of the segment it currently belongs to, that is:

$

In each binary-splitting round, we want to determine whether each node is in the left half or the right half of its current segment.

Consider processing all segments in parallel by grouping their indices modulo

$.

For

$, we make one query:

• if

$, set

$; - otherwise, set

$.

This query can split all nodes satisfying

$.

Consider a node

$ whose side we want to determine, and suppose the index of its segment is

$. The only nodes that can actually affect it are those in the previous segment

$.

All other selected segments are at least two full depth segments away from the segment of

$, so their distance to

$ must be greater than

$, and they will not light up

$.

Therefore:

• if

$ is in the left half of its current segment, then after moving

$ steps towards the root, it reaches the previous segment, so it will be lit up; - if

$ is in the right half of its current segment, then its distance to every node in the previous segment is greater than

$, so it will not be lit up.

Thus, from the query result, we can directly determine which half

$ should enter.

There is also the case

$: the first segment has no previous segment, so we additionally need to set

$ for the root.

Each round only needs

$ queries, and there are

$ rounds. Therefore, the number of queries needed to find all depths is at most:

$.

In fact, with some small optimizations, the number of queries can be reduced by a few more. Also, this method is more consistent with the official editorial's method for finding the parent of each node.

Translated with the assistance of ChatGPT.