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 set $$$B = 140$$$. 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?

Auto comment: topic has been updated by SkyWave2024 (previous revision, new revision, compare).