Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: Josh
As 
~2^{17} \approx 100\,000~, we should aim for a solution with approximately 
~\log_2 N~ queries.
Subtask 1
At any time, the possible values of 
~X~ form a potential range. When we query a suspect 
~Y~, we can determine whether ~X~ is equal to ~Y~, greater than ~Y~, or less than ~Y~. Hence, we can simply binary search for the value of ~X~, using approximately ~\log_2 N~ queries.
Subtask 2
At any time, the possible values of ~X~ form a (non-rooted) subtree. Consider querying suspect ~Y~ such that ~Y~ is part of the subtree, and rooting the tree of ~Y~. Then, our query tells us which (rooted) subtree of the children of ~Y~ contains ~X~.
Thus, we can root the tree at node 
~1~. After each query, we simply descend to the left or right subtree of the current node, depending on which subtree the return value of the query lies in.
Subtask 3
We can optimise our subtask 
~2~ solution to work on a general graph. Given a (non-rooted) tree that ~X~ could lie in, we need to determine the optimal ~Y~ to query. Recall that after querying ~Y~, if we have not yet found ~X~, then our new tree could be any of the subtrees formed when removing ~Y~.
As we are looking for a solution with approximately ~\log_2 N~ queries, we should choose a value of ~Y~ such that the maximum size of any subtree formed when removing ~Y~ is at most half the size of the current tree. This would allow us to reduce the size of the possible set of values of ~X~ by half in each query. To do so, we should choose ~Y~ to be the centroid of the current tree.
Comments