This is a past hiring challenge https://www.hackerearth.com/challenges/hiring/lazypay-java-developer-hiring-challenge-2019/

Question :

**Tree Play**

Given a tree with N vertices and N - 1 edges. Every vertex has stone piles kept on them given on them given by array Stones. **Bob** and **Alex** plays game of Q rounds. In each round piles in path from vertex u to v are considered. Both of them play in alternate turns. In each turns, a player can choose only one pile and remove any number of stones (at least one) from that pile.The player who cannot move is considered to lose the game. **Bob** always start first, Print winner after every round if both of them play optimally.

**Input**

**First line :** N,Q, no. of vertices and no. of round respectively

**Second line :** N integers defining array stones.

**Next N-1 lines :** u and v, meaning there is an edge between vertex u and u.

**Next Q lines :** u and v for i^{th} round.

**Output**

For each round print winner as **Alex** or **Bob** in new line.

**Constraints**

1 \leq N, Q \leq 2 \times 10^5

1 \leq u, v \leq N

1 \leq Stones_i \leq 10^5

**Sample Input**

8 \> 4

2 \> 3 \> 4 \> 4 \> 2 \> 3 \> 2 \> 1

1 \> 2

1 \> 3

2 \> 4

2 \> 5

5 \> 6

6 \> 7

4 \> 8

3 \> 6

4 \> 4

1 \> 6

4 \> 7

**Sample Output**

Bob

Bob

Alex

Bob

**Explanation**

For round two there is only one pile containing 4 stones. **Bob** will pick up all the stones and winds the game as **Alex** can’t pick up further.

**Time limit :** 1 sec.

I found out clearly this is nim game https://www.geeksforgeeks.org/combinatorial-game-theory-set-2-game-nim/

My approach :

So I have to just xor the values of each nodes in the path and check whether it is zero or not. If it is 0 then Alex win otherwise Bob.

I am getting Runtime error in many case and TLE in others. I don’t understand what is wrong in my code.

My Solution :

```
static class Pair {
boolean isPath; // whether the path exits or not
int xor; // xor value
Pair(boolean isPath, int xor) { // Constructor
this.isPath = isPath;
this.xor = xor;
}
}
static class Graph {
int V;
LinkedList<Integer>[] adj;
int[] val;
Graph(int V) {
this.V = V;
adj = new LinkedList[V + 1];
for (int i = 0; i <= V; ++i) {
adj[i] = new LinkedList<>();
}
val = new int[V + 1];
}
void addEdge(int u, int v) { // undirected graph edges u to v and backedge v to u
adj[u].add(v);
adj[v].add(u);
}
Pair DepthFirstSearch(int s, int d, boolean[] visited) {
visited[s] = true;
if(s == d) {
return new Pair(true, val[s]); // is we reach destination then return Pair(path exits , value of the path)
}
for (int i = 0; i < adj[s].size(); ++i) { // calling on adjacency list
if(!visited[adj[s].get(i)]) {
Pair temp = DepthFirstSearch(adj[s].get(i), d, visited);
if(temp.isPath) {
return new Pair(true , temp.xor ^ val[s]); // xor the current node value with every child node value in path
}
}
}
return new Pair(false, 0); // path does not exits
}
boolean DFS(int s, int d) { // dfs from source to destination
boolean[] traversed = new boolean[V + 1]; // visited array
Pair p = DepthFirstSearch(s, d, traversed); // calling dfs
return p.xor == 0; // if xor value is 0 or not
}
}
/*
8 4
2 3 4 4 2 3 2 1
1 2
1 3
2 4
2 5
5 6
6 7
4 8
3 6
4 4
1 6
4 7
*/
static class Code {
private void solve(InputReader in, OutputWriter out) {
int n = in.readInt(); // number of vertices in tree
int query = in.readInt(); // number of query
Graph graph = new Graph(n); // initialize tree with n nodes
for(int i = 1; i <= n; ++i) {
graph.val[i] = in.readInt(); // initialize value of each node
}
for(int i = 0; i < n - 1; ++i) {
graph.addEdge(in.readInt(), in.readInt()); // add edges
}
for(int i = 0; i < query; ++i) {
if(graph.DFS(in.readInt(), in.readInt())) {
out.printLine("Alex");
}
else {
out.printLine("Bob");
}
}
}
}
```