ENOC1 - Editorial

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

2 Likes