PROBLEM LINK:Author: Ivan Fekete 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 DepthFirst 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_{u} xor S_{v}). Edges of the chain starting from the root and ending at 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 DepthFirstSearch, and keep for the i^{th} node a variable st_{i} (denoting the value of the timer once entering this node),and a variable en_{i} 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^{th} node by interval [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
This question is marked "community wiki".
asked 15 Jul '17, 08:10

Thanks to this problem I learned few new things. For beginners who are facing difficulty solving this (like i did) I recommend following steps 
I hope above helps :) answered 19 Jul '17, 17:14

Can someone please explain what if root node is in between path of u and v. Now if we take xor S[u] and S[v] then we will take xor of root node twice which will eliminate the contribution of node from the xor since root is taken twice and it vanishes and becomes 0. But that was not intended because root node was a part of the path . Have I got something wrong. Please Help. answered 25 Jul '17, 23:00
@deadwing97 please clear my doubt.
(25 Jul '17, 23:38)
2
In the problem, the V values are attached to edges between two adjacent nodes. In the Editorialist's solution, the values are attached to the node more distant from the root node. There is some logic
There is no V associated with the root node, Hope that makes sense.
(26 Jul '17, 01:52)
@john_smith so i can say that if u to v has to include root it must be the lca of both those nodes(possibly) and in case of that there is no problem because we can take xor as mentioned above without any problem and if root node is the lca then there will be no edge whose xor is to be taken with themselves.Is this correct? Thank you for your reply:)
(26 Jul '17, 11:21)

in the editorial solution they have binary index tree to store the value.... i tried to use the soln given using segment tree but it is giving wrong answer .... can anyone tell me what is wrong in my code? here is the code answered 30 Jul '17, 17:06
