Here is a method to find the depth of every node in $$$3\log n$$$ operations.↵
↵
Root the tree at $$$1$$1$, and let $$$dep_1=0$$$.↵
↵
Take a power of two $$$D$$D$ such that $$$D\ge n$$$. Since the depth of any node in the tree is less than $$$n$$n$, initially we can assume that the depth of every non-root node lies in $$$[1,D]$$$.↵
↵
Then we keep binary-splitting this interval.↵
↵
Suppose that currently every node belongs to a depth segment of length$$$len$$$. For a node $$$u$$u$, let $$$id_u$$$ be the index of the segment it currently belongs to, that is:↵
↵
$$$↵
dep_u\in[id_u len+1,(id_u+1)len]↵
$$$↵
↵
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 $$$3$$3$.↵
↵
For$$$r=0,1,2$$$, we make one query:↵
↵
- if$$$id_u\equiv r\pmod 3$$$, set $$$d_u=\frac{len}{2}$$$;↵
- otherwise, set$$$d_u=0$$$.↵
↵
This query can split all nodes satisfying$$$id_u\equiv r+1\pmod 3$$$.↵
↵
Consider a node $$$x$$x$ whose side we want to determine, and suppose the index of its segment is $$$id$$$. The only nodes that can actually affect it are those in the previous segment $$$id-1$$$.↵
↵
All other selected segments are at least two full depth segments away from the segment of $$$x$$x$, so their distance to $$$x$$x$ must be greater than $$$mid$$$, and they will not light up $$$x$$x$.↵
↵
Therefore:↵
↵
- if $$$x$$x$ is in the left half of its current segment, then after moving $$$mid$$$ steps towards the root, it reaches the previous segment, so it will be lit up;↵
- if $$$x$$x$ is in the right half of its current segment, then its distance to every node in the previous segment is greater than $$$mid$$$, so it will not be lit up.↵
↵
Thus, from the query result, we can directly determine which half $$$x$$x$ should enter.↵
↵
There is also the case$$$id=0$$$: the first segment has no previous segment, so we additionally need to set $$$d_1=mid$$$ for the root.↵
↵
Each round only needs $$$3$$3$ queries, and there are $$$\log D$$$ rounds. Therefore, the number of queries needed to find all depths is at most: $$$3\log_2 1024=30$$$.↵
↵
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.
↵
Root the tree at $
↵
Take a power of two $
↵
Then we keep binary-splitting this interval.↵
↵
Suppose that currently every node belongs to a depth segment of length
↵
dep_u\in[id_u len+1,(id_u+1)len]↵
$$
↵
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
↵
- if
- otherwise, set
↵
This query can split all nodes satisfying
↵
Consider a node $
↵
All other selected segments are at least two full depth segments away from the segment of $
↵
Therefore:↵
↵
- if $
- if $
↵
Thus, from the query result, we can directly determine which half $
↵
There is also the case
↵
Each round only needs $
↵
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.
