Max XOR Subtree Query - MotorQ Online Assessment

Problem Preview

"You are given a rooted tree with **N** vertices (numbered 1 through **N**); vertex 1 is the root. Each vertex has a weight; let's denote the weight of vertex **i** by **w_i**. You should answer **Q** queries. The queries have to be processed online, i.e. to obtain each query, you need the answer to the previous query. In each query, you are given a vertex **v** and a parameter **k**. For each vertex **u** in the subtree of **v** (including **v**), consider the value **w_u** $\oplus$ **k** ($\oplus$ denotes the bitwise XOR operation). The answer to this query is the maximum of these values and the smallest **u** such that vertex **u** is in the subtree of vertex **v** and **w_u** $\oplus$ **k** is equal to this maximum. --- ### Input * The first line of the input contains a single integer **T** denoting the number of test cases. The description of **T** test cases follows. * The first line of each test case contains two space-separated integers **N** and **Q**. * The second line contains **N** space-separated integers **w_1, w_2, ..., w_N**. * Each of the next **N - 1** lines contains two space-separated integers **x** and **y** denoting that there is an edge between nodes **x** and **y**. * The next **Q** lines describe queries. Each of these lines contains two space-separated integers **a** and **b**. The parameters **v** and **k** can be obtained in the following way: let's denote the value and vertex from the answer to the previous query by **x_l** and **v_l** respectively (**x_l = v_l = 0** if this is the first query); then, **v = a** $\oplus$ **v_l** and **k = b** $\oplus$ **x_l**. --- ### Output For each query, print a single line containing two space-separated integers — the answer to the query, i.e. the number of the vertex for which we get the maximum value and the maximum value. --- ### Constraints * 1 <= **T** <= 1,000 * 1 <= **N** <= 2 * 10^5 * 1 <= **Q** <= 10^6 * 1 <= **x, y, v** <= **N** * 1 <= **w_i** < 2^20 for each valid **i** * 1 <= **k** < 2^20 * the sum of **N** over all test cases does not exceed 2 * 10^5 * the sum of **Q** over all test cases does not exceed 10^6 --- ### Subtasks **Subtask #1 (10 points):** * the sum of **N** over all test cases does not exceed 5,000 * the sum of **Q** over all test cases does not exceed 5,000 **Subtask #2 (15 points):** * the sum of **N** over all test cases does not exceed 2,000 * the sum of **Q** over all test cases does not exceed 10^6 **Subtask #3 (75 points):** original constraints --- ### Sample 1: **Input** ```text 1 10 5 9 17 93 16 3 61 23 11 2 1 1 2 2 5 5 8 1 3 1 4 3 6 3 7 6 9 6 10 4 14 7 123 5 103 9 32 5 118 ``` **Output** ```text 4 30 7 114 8 30 3 99 6 40 ``` --- ### More Info * **Time limit:** 2 secs"