Graph Theory,Sorting,Data Structures
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
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 Si 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 (Su xor Sv). 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 Depth-First-Search, and keep for the ith node a variable sti (denoting the value of the timer once entering this node),and a variable eni 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 ith node by interval [sti , eni]
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
Si = Si xor V
for each i : (stv ≤ i ≤ env)
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[sti] = X[sti] xor V
This means that we are adding V to the xor sum of all nodes with enterance timer ≥ stv
X[eni + 1] = X[eni + 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 Si is:
Si = X1 xor X2 xor X3 xor X4 xor X5 xor … Xi
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))