Imagine a network of \(N \) points connected by \(N-1\) lines, forming a tree-like structure. Every point has a number assigned to it, given as an array \(Arr\) of size \(N\). Now, you need to answer \(Q\) queries. In each query, you're asked to do the following:
- Pick any number from \(0\) to \(X\) (inclusive). Let's refer to this number \(α\).
- Temporarily change each point's number to the Bitwise XOR result of that point's initial value and \(α\).
- After the above modification, determine the maximum value that can be obtained by performing a Bitwise XOR operation on all numbers on points that lie on the simple path between points \(A\) and \(B\) (including \(A\) & \(B\)).
Note: A simple path is a path in a tree that does not have repeating points.
Input Format:
- The first line contains a single integer \(T\), which denotes the number of test cases.
- For each test case:
- The first line contains \(N\) denoting the number of points.
- The following \(N-1\) lines contain 2 space-separated integers, \(U\) & \(V\) indicating that there is a link between points \(U\) & \(V\)
- The second line contains \(N\) space-separated integers, denoting the numbers assigned to every point.
- The next line contains \(Q\) denoting the number of queries.
- The next \(Q\) lines contain 3 space-separated integers, \(X\), \(A\) and \(B\).
Output Format:
For each test case, answer all the \(Q\) queries. For each query, print in a new line the maximum Bitwise XOR result of all the numbers on points that lie on the simple path between points \(A\) and \(B\) (inclusive) for each query that you can get after choosing a number \(α\), which lies between \(0\) & \(X\) (inclusive), and each points value has been temporarily modified to Bitwise XOR result of the initial value of that point and \(α\).
Constraints:
1 5 1 2 1 3 2 4 2 5 7 9 3 0 4 2 10 5 1 1 2 3
15 13
The first line denotes T = 1.
For test case \(1\):
We are given:
- N = 5, M = 1, and the points are linked as follows:
- The numbers on points are : [7, 9, 3, 0, 4]
Now,
- For the first query, we are given X=10, A=5, and B=1.
- If we choose,
- α = 5 (0 ≤ α ≤ 10), to modify each point's value, has to Bitwise XOR result of the initial value of that point and α.
- The new numbers on points are : [2, 12, 6, 5, 1]
- The points that lie on the simple path between points 5 and 1 (including 5 and 1) are 5, 2 & 1.
- The Bitwise XOR result of the numbers on points 5, 2 & 1 ⇒ (1⊕12⊕2) ⇒ 15. It can be proved that 15 is the maximum value of Bitwise XOR that we can get.
- Hence, the answer to this query is 15.
- If we choose,
- For the first query, we are given X=1, A=2, and B=3.
- If we choose,
- α = 0 (0 ≤ α ≤ 1), to modify each point's value has to Bitwise XOR result of the initial value of that point and α.
- The new numbers on points are : [7, 9, 3, 0, 4]
- The points that lie on the simple path between points 2 and 3 (including 2 and 3) are 2, 1 & 3.
- The Bitwise XOR result of the numbers on points 2, 1 & 3 ⇒ (9⊕7⊕3) ⇒ 13. It can be proved that 13 is the maximum value of Bitwise XOR that we can get.
- Hence, the answer to this query is 13.
- If we choose,
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor