The basic idea is, set a value $$$B$$$, if a subtree's maxinum height is smaller than $$$B$$$ then it's useless because after $$$B$$$ queries it will jump out of the subtree. If there are $$$y$$$ sons of $$$u$$$ satisfying maxinum height greater than $$$B$$$, let's ask $$$y - 1$$$ of them and if none of these queries return $$$1$$$ then we go to the remained son's subtree. We can get a chain.

Now keep asking a leaf to make the queries number up to $$$B$$$, then $$$x$$$ is on chain we get, so do a binary search. The total queries number is $$$B + \log n$$$.

I don't know how to prove $$$\sum y - 1 \le B$$$, maybe it's totally wrong. But:

• For E1, I set $$$B = 280$$$. After I get AC, I found that there are two big bugs in my code:
• I did not use a subtree's maxinum height is smaller than $$$B$$$, but use a subtree's maxinum height is smaller than $$$B + now$$$ ($$$now$$$ is the queries number i have done) to judge if a substree is useless.
• After I get the chain, I do $$$B$$$ queries on a leaf instead of making the queries number up to $$$B$$$.
• Why this can get AC?
• For E2, i fixed bugs above and get WA on pretest 49. After contest, I use a subtree's maxinum height is smaller than $$$B + 3$$$, to judge if a substree is useless and i get AC. Why?

My E1 code: 271595615

My E2 code: 271694519

Can anyone hack then?