Practice : Click here

Contest : Click here

**Author** : Soham Chakrabarti

**Tester** : Arkapravo Ghosh

**Editorialist** : Soham Chakrabarti

### Difficulty :

Easy - Medium

### PREREQUISITES:

Lowest Common Ancenstor, Dp on trees

### PROBLEM:

Given a tree with N nodes and N−1 edges and Q queries, find the XOR of the shortest path from node u to v.

### EXPLANATION:

Having knowledge of **LCA** is essential. Click to read more about lowest common ancestor of two nodes.

Coming to the problem, we have to store the XOR of nodes in a DP table as there is going to be queries ( Q \le 10^5 ).

We are going to build the DP table using Binary Lifting of Nodes.

## Build DP table

void dfs(int u, int par, int v = -1, int h=0)

{

lvl[u] = h;

up[u][0] = par;

if(v!=-1)dp[u][0]=v;

FR(i,1,LG+1)

{

up[u][i] = up[up[u][i-1]][i-1];

dp[u][i] = (dp[u][i-1] ^ dp[up[u][i-1]][i-1]);

}

for(auto x:G[u])

{

if(x != par) dfs(x, u, val[x], h+1);

}

}

After successfully building the DP table storing XOR, we take every query containing the two nodes u and v and get the LCA of the two nodes.

Let us take `x = lca(u,v)`

,

By taking data from the DP table, we go from node to node ( u to x ) and ( v to x ) and keep XOR-*ing* the result. (considering some cases)

### LINKS:

**Author’s Solution** : Click here

**Tester’s Solution** : Click here