### 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