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?

Let's do HLD on the tree and now this problem is on a sequence : Given an array $$$a$$$ of length $$$m$$$, answer $$$q$$$ queries, each query gives you $$$x,y$$$ and you need to print $$$\sum \limits_{i=0}^y a_i \oplus(x+i)$$$ or $$$\sum \limits_{i=0}^y a_i \oplus(x-i)$$$.

Let's calculate the answer for each bit $$$j$$$. You can easily find that $$$x,x+1,\ldots,y$$$ in $$$j$$$-th bit looks like $$$0000111100001111\ldots$$$, set a value $$$B$$$.

• For bit $$$j \le B$$$, there are at most $$$\mathcal O(2^j)$$$ distinct $$$x$$$ (as the length of a pattern is $$$2^{j+1}$$$). Calculate all distinct $$$x$$$ by brute force and the complexity is $$$\mathcal O(\sum \limits_{j=0}^B m2^j) = \mathcal O(m2^B)$$$.
• For bit $$$j > B$$$, the same pattern repeats $$$\mathcal O(\dfrac{m}{2^j})$$$ times. Pre-calculate the prefix sum of numbers of $$$0,1$$$ in $$$a_i$$$'s $$$j$$$-th bit and we can solve a query in $$$\mathcal O(\dfrac{m}{2^j})$$$. The complexity here is $$$\mathcal O(\dfrac{mq \log n}{2^j})$$$.

Let $$$2^B = \sqrt {m \log n}$$$, The overall complexity is $$$\mathcal O((n+q) \sqrt {n \log n})$$$. But you know HLD runs really fast so it can pass the tests in $$$2.5$$$ seconds :)

Can anyone hack me? My submission.

In this blog, zh0ukangyang was banned because of the policy of using a single account. Few days passed, PinkieRabbit reached legendary grandmaster by Codeforces Round 941 (Div. 1). However, he was found as a cheater in this blog. He broke the rule of codeforces contest. We could clearly know that 'The contestants are forbidden to talk about subjects, related to the problems, with anybody, including other contestants' in Mike's blog. FIVE days passed, there is nothing happened to PinkRabbit. Is it too hard for Mike to solve this problem? I don't think so. The evidence is certain. So I can say there is no justice in codeforces?