Medium Graph Theory > Breadth First Search/Depth First Search

![enter image description here][1] **XORO** is a very destructive boy ( Be careful with him !! ) who lives in country called XorDesh. There are total N cities in the country. The structure of the country is such that from any city you can reach to any other city. R is the capital city of the country. XORO may reside in any cities in XorDesh , say city X. Each city of the country contain some amount gold value in it. XORO is planning to destroy these gold values by using his destructive power. His destructive power is represented as an integer value K. If he apply bitwise xor operation of his city's gold value with the gold value of particular city and if he obtain exactly K value then, he can destroy that gold value of that particular city easily. Xoro has a destructive plan that whichever city he reside in XorDesh, he always tries to move to Capital city R following shortest possible path andhe tries to destroy gold values of cities encountered in that path. The XorDesh city structure can be regarded as rooted tree with **N** nodes and root of the tree is Capital city **R**. Each node of that tree contain some value in it. You have to answer several queries. For each query you will be given two integer representing node **X** and value **K**, representing respectively City where XORO reside and destructive power XORO has. You have to answer how many gold values he will destroy by following his destructive plan. Input: ------ Input starts with an integer **T (T<=1<=10)**, denoting the number of test cases. Each case contains three integer **N (2 ≤ N ≤ 100000)** , denoting the number of nodes and **Q (1<=Q<=100000**) ,denoting numbers of test cases and **R ( 1<=R<=N)** ,denoting root of the tree . The next line will contain **N** integers separated by spaces, denoting the values of node from **1** to **N**. Each of these integers will be non negative integer upto **1000000000**. The next **N-1** lines will contain two integers **U and V ( 1<= U,V<=N )** representing there is an edge between them. Then finally, there will be **Q** lines with two integers **X** and **K**, as described in the problem statement. Output: ------- For each case of input, print the case number as in sample format and print **Q** lines representing answer for each query. Sample Input ------------ 1 4 4 1 3 3 1 2 1 2 2 4 2 3 3 2 4 1 3 1 2 0 Sample Output ------------- Case 1: 2 2 0 1 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/b225a922-5afa-cf64-d6df-08d46fa7636e_24b412d0791b43b59b27d34ddb6d03c1_W188xH201.png

Bishal Gautam