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