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.