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,iI 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: [submission:271595615]↵
↵
My E2 code: [submission:271694519]↵
↵
Can anyone hack then?
↵
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,
↵
My E1 code: [submission:271595615]↵
↵
My E2 code: [submission:271694519]↵
↵
Can anyone hack then?
