### SkyWave2024's blog

By SkyWave2024, history, 2 weeks ago,

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?

• +8

 » 2 weeks ago, # |   0 Auto comment: topic has been updated by SkyWave2024 (previous revision, new revision, compare).