PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Harsh Shah
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Segment Tree Lazy propagation, Exclusive or, Basic graphs
PROBLEM:
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.
EXPLANATION:
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 AND TESTER’S SOLUTIONS:
Author’s solution can be found here