### PROBLEM LINK:

**Author:** Ivan Fekete

**Primary Tester:** Misha Chorniy

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Medium

### PREREQUISITES:

Graph Theory,Sorting,Data Structures

### PROBLEM:

Given a rooted weighted tree with **N** nodes and **M** queries of the form **(u , v , K)**. For each query, you must report to **xor** sum of edges which has weight less than or equal to **K** on the path from **u** to **v**.

**N,M ≤ 10^5**

### EXPLANATION:

First of all let’s solve the easier version of this problem. Queries which asks for the xor sum of edges on the path between 2 fixed nodes **(without the restriction of K).**

Let’s choose an arbitrary root for our tree and call a Depth-First search starting from this node.Let’s maintain a table **S[N]**, such that **S _{i}** denotes the

**xor**sum of edges weights starting from the

**root**and ending at node

**i**. The answer of each query

**(u,v)**would be

**(S**. Edges of the chain starting from the root and ending at

_{u}xor S_{v})**LCA(u,v)**(lowest common ancestor) would be excluded because

**(V xor V = 0)**.

Now let’s solve our problem. First thing we should take advantage of, is that we can answer our queries offline (reading then processing all queries, after that reporting the answer of each one).

Each edge weighted **W** must be included in the answer of all queries with **K ≥ W**. For queries with **K < W** we can assume that this edge’s weight is zero (so it won’t affect the answers).

Let’s sort our queries in ascending order according to their magic numbers **K**, and sort our edges in ascending order according to their weights **W**. Let’s process our queries in ascending order, and maintain a pointer iterating on our sorted edges list. So before processing a query with magic number **K**, we add all edges with **W ≤ K** through our pointer.

Now Let’s discuss adding edges, and how will we get our table S[].

Let’s maintain a timer incremented by one every time we visit a new node in our Depth-First-Search, and keep for the **i ^{th}** node a variable

**st**(denoting the value of the timer once entering this node),and a variable

_{i}**en**denoting the value of the timer after finishing this node’s subtree (before exiting). This is a famous technique called euler tour on tree (dfs order). So we can represent nodes located in the subtree of the

_{i}**i**node by interval

^{th}**[st**

_{i}, en_{i}]Regarding adding edges, each edge will link between 2 nodes **(u,v)** such that **u = par[v]**, this edge’s weight will be added to the **xor sum** (cumulative xor sum from the root) of all nodes located in the subtree of **v**. That means we should apply the operation

**S _{i} = S_{i} xor V**

for each **i** : **(st _{v} ≤ i ≤ en_{v})**

This can be done using a binary indexed tree, segment tree (with/without) lazy probagation. Since our modification query is done on a segment of array **S** and we are querying the value of only one element we can do the following:

Let’s maintain an array **X** which is all zeros at the beginning. When handling an edge of weight **W** added to the results of nodes in node v subtree.

**X[st _{i}] = X[st_{i}] xor V**

This means that we are adding V to the **xor** sum of all nodes with enterance **timer ≥ st _{v}**

**X[en _{i} + 1] = X[en_{i} + 1] xor V**

This means that we are excluding **V** from the **xor** sum of all elements with entrance **timer > en[v]** (since it was added in the first operation so doing **xor** again is equivalent to exclusion).

You can notice now that the value of **S _{i}** is:

**S _{i} = X_{1} xor X_{2} xor X_{3} xor X_{4} xor X_{5} xor … X_{i}**

Now we can easily iterate through our queries, and for each one we should make sure that all edges with weight less than or equal to this query magic number are added. After that, each query can be solved in O(log N).

Total complexity **O(N log N + M (log M + log N))**

### AUTHOR’S AND TESTER’S SOLUTIONS:

**AUTHOR’s solution**: Will be found here

**TESTER’s solution**: Will be found here

**EDITORIALIST’s solution**: Will be found here