Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 7 Nov, 2021

Hard

```
Here XOR denotes the bitwise operator (^).
```

```
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, ‘N’ and 'Q', denoting the number of nodes and the total queries operation to be performed.
The next ‘N’-1 lines of each test case contain two integers representing an edge between the given indices.
The next line of each test case contains ‘Q’ space-separated integers denoting the nodes of the tree on which query has to be performed.
```

```
For each test case, print ‘Q’ space-separated integers denoting the result of the queries.
Print the output of each test case in a separate line.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
0 <= N, Q <= 10^5
0 <= QUERY[i] < N
Time Limit: 1 sec
```

The basic idea is to traverse the subtree for each given node in the query. We traverse the nodes using the DFS and compute the XOR value of the subtree while traversing the tree.

- Create a graph (say, ‘GRAPH’) using the ‘EDGES’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
- Create an array (say, ‘RES’) to store the result of queries.
- Run a loop from 0 to ‘Q’ (say, iterator ‘i’) to traverse the queries.
- Call the
**DFS**function to compute the XOR of the subtree and store the value returned by the function in the ‘RES’.

- Call the
- Return ‘RES’.

**DFS**(‘GRAPH’, ‘CURR’, ‘PREV’) (where ‘CURR’ is the current vertex and ‘PREV’ is the previous vertex traversed).

- Create a variable (say, ‘VAL’) to store the XOR value and initialize it with ‘CURR’.
- Traverse the adjacent vertices of the ‘CURR’ vertex (say, ‘V’)
- Check if ‘V’ is not equal to ‘PREV’
- Recursively call the
**DFS**function to traverse the tree and update the ‘VAL’ by taking the XOR of it by the value returned by the function.

- Recursively call the

- Check if ‘V’ is not equal to ‘PREV’
- Return ‘VAL’.

The basic idea is to precompute the XOR of all the nodes of the sub-tree by traversing the tree. We start by storing the XOR values from the child node and then using the value of the child node for calculating the XOR values of all the nodes of the sub-tree of the parent node. We store these values in an array (say, ‘DP’) and then answer the queries in constant time.

**Here is the algorithm :**

- Create a graph (say, ‘GRAPH’) using the ‘EDGES’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
- Create an array (say, ‘DP’) to store the pre-computed XOR values.
- Call the function
**DFS**to compute the values. - Create an array (say, ‘RES’) to store the result of queries.
- Run a loop from 0 to ‘Q’ (say, iterator ‘i’) to traverse the queries.
- Push ‘DP[QUERY[i]]’ in the ‘RES’.

- Return ‘RES’.

**DFS**(‘GRAPH’, ‘CURR’, ‘PREV’, ‘DP’) (where ‘CURR’ is the current vertex and ‘PREV’ is the previous vertex traversed).

- Create a variable (say, ‘VAL’) to store the XOR value and initialize it with ‘CURR’.
- Traverse the adjacent vertices of the ‘CURR’ vertex (say, ‘V’)
- Check if ‘V’ is not equal to ‘PREV’
- Recursively call the
**DFS**function to traverse the tree and update the ‘VAL’ by taking the XOR of it by the value returned by the function.

- Recursively call the

- Check if ‘V’ is not equal to ‘PREV’
- Update ‘DP[CURR]’ with ‘VAL’.
- Return ‘VAL’.