### PROBLEM LINK:

**Author:** Constantine Sokol

**Tester:** Pavel Sheftelevich

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

medium-hard

### PREREQUISITES:

Sqrt decomposition

### PROBLEM:

Let’s define bitTwister(x, y) function using the following code snippet written in Python:

def bitTwister(x, y): x ^= x >> 11 x ^= (x << 7) & 2636928640 x ^= (x <> 18) return (1812433253 * (x ^ (x >> 30)) + y) & 4294967295

You are given a tree T consisting of n nodes.

Let’s define children(v) as a sequence of the children of v placed in the increasing order of their ids.

We define children(v, d) as following.

- children(v, 0) = [v]
- children(v, 1) = children(v)
- children(v, d) = children(children(v)[1], d - 1) + children(children(v)[2], d - 1) + ... + children(children(v)[|children(v)|], d - 1) if d > 1

Let’s define reducedByBitTwister(X_1, X_2, ..., X_k) as following:

reducedByBitTwister(X_1) = X_1

reducedByBitTwister(X_1, ..., X_{k - 1}, X_k) = bitTwister(reducedByBitTwister(X_1, ..., X_{k - 1}), X_k) if k > 1

Your are asked to process Q queries of the following kind: given two integers v and d (1 ≤ v ≤ n), let’s denote children(v, d) as a node sequence V1, V2, …, Vk. Your should calculate reducedByBitTwister(A_{V_1}, ..., A_{V_k}). It’s guaranteed, that children(v, d) is a non-empty sequence for each query.

### QUICK EXPLANATION:

For each of the queries, let’s find (l, r) - the leftmost and the rightmost children of v on the d'th level. After that, let’s calculate the answer in \mathcal{O}(|\text{children of v on the d'th level}|) and memoize it - if we’ll get the same pair (l, r) later, we’ll just return the value without calculating it again.

It can be shown, that such the sum of $\mathcal{O}(|\text{children of v on the }d{'th level}|) all over the testcases is no more than \mathcal{O}(n , sqrt , n)$.

The total complexity is \mathcal{O}(q * log n + n * sqrt \, n).

### EXPLANATION:

Detailed explanation of the proof of time complexity being \mathcal{O}(n \, sqrt \, n) will be added later. Please have a look at tester’s solution for a very clean implementation of the approach.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.