NPLELE - Editorial




Author: Aniket Marlapalle

Tester: Harsh Shah

Editorialist: Harsh Shah




Segment Tree Lazy propagation, Exclusive or, Basic graphs


Given a weighted tree, handle two types of queries. 1. Update the weight of an edge. 2. Find the xor of the path from node u to v.


Lets denote the xor of all edges from node u to v as X(u-v).
One can easily make following findings.
X(root-u)=X(root-L) xor X(L-u) where L is LCA(u,v) as LCA(u,v) definitely lies on the path from u to root (1)

Now, X(u-v) = X(u-L) xor X(v-L)

xoring on RHS twice by X(root-L)

X(u-v) = X(u-L) xor X(root-L) xor X(v-L) xor X(root-L)

From conclusion 1,

X(u-v) = X(root-u) xor X(root-v)

Hence now if we somehow maintain every time the xor from root to every node u, denoting by XRoot(u), our task is easy. To achieve this, one needs to make a simple observation that an edge contributes to XRoot(u) of the nodes that falls in the subtree of its node of greater depth. For instance, consider an edge e between node u and v, depth of u being d and that of v being d+1. The edge e contributes to XRoot(w) where w lies in subtree of node v.

Hence the tree can be converted to an array by a DFS. Then segment tree can be created on XRoot values of that array. Now the two queries can be handled as:

On every update query, make a range update on segment tree on subtree of the node of greater depth
(as explained above).
On every query u-v, print pointQuery(u) xor pointQuery(v).

Refer the code for implementation details.


Author’s solution can be found here

1 Like