Easy - Medium
Lowest Common Ancenstor, Dp on trees
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.
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] = par;
up[u][i] = up[up[u][i-1]][i-1];
dp[u][i] = (dp[u][i-1] ^ dp[up[u][i-1]][i-1]);
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)
Author’s Solution : Click here
Tester’s Solution : Click here