PROBLEM LINK:
Author: Utkarsh Saxena
Tester: Alexey Zayakin
Editorialist: Utkarsh Saxena
PROBLEM
You are given a Tree of N vertices and N-1 weighted edges. The weights of edges are unknown. You will be given a pairs of vertices u,\space v and xor-sum of all edges lying on the path from u to v. You need to tell which information contradicts all the information given before that.
Constraints: N \le 10^5, Q \le 2*10^5
PREREQUISITES
EXPLANATION
Denote X_u = xor-sum of edges on the path from root(say 1) to u. Denote F(u,v) = Xor-sum of edges on the path from u to v = X_u\oplus X_v. The array X can uniquely identify the edge weights of the tree. Array X is the only unknown implying that we don’t need to know the structure of the tree in order to answer the problem. Only calculating the correct array X would suffice.
In this problem you are given values of F(u,v) for multiple pairs u,v. But F(u,v) = X_u\oplus X_v . This means you are given xor-sum of many pairs of numbers. We can now totally forget that this actually represents a xor of path on the original tree.
Modified problem
Given xor of some pairs of numbers, calculate xor of some other pair of numbers. Eg: Given values of a\oplus b and b\oplus c, find value of a\oplus c.
Example 1:
- Given a\oplus b, b\oplus c and c\oplus d
- Find a\oplus d
- Answer = (a\oplus b)\oplus (b\oplus c)\oplus (c\oplus d)
Example 2:
- Given a\oplus b, b\oplus c and d\oplus e
- Find a\oplus e
- This question cannot be answered.
From this we can observe that to answer xor of two numbers, we need to make a graph of all known information. Eg: If we know that a\oplus b = x then we need to make an edge between a and b with weight x. Xor of two numbers can be found iff they lie in the same connected component. Xor of two numbers lying in the same component can be found by tracing a path between the numbers. This is what we have done in Example 1.
Tracing the path between a pair of number is too slow. Lets try to calculate the xor of two numbers(lying in the same component) faster. For each component C we maintain an array A_C. A_C[i] will denote xor of i^{th} number and a fixed number f in component C. If we have this A_C array calculated, answering the xor of a and b lying in component C = A_C[a] \oplus A_C[b].
Also note that the answer to the query is independent of f. The answer to the query does not change even if we apply the transformation A_C[i] = A_C[i] \oplus X for each each i in C and for any integer X. This is because answer to the query A_C[a] \oplus A_C[b] cancels any transformation that is applied to both the a and b.
When new information comes F(u,v)=x such that u and v lie in different components, we will need to merge the two components. Let u lie in component C1 and v in component C2. Let the merged component be called C. We will have to calculate a new A_C using old A_{C1}, A_{C2} and F(u,v). A_C will satisfy:
- A_C[i] = A_{C1}[i] for all i in C1. This ensures information of C1 is stored.
- A_C[i] \oplus A_C[j] = A_{C2}[i] \oplus A_{C2}[j] for all i, j in C2. This ensures information of C2 is stored.
- A_C[u] \oplus A_C[v] = x. This ensures the new information is stored.
\implies A_C[v] = x \oplus A_C[u]
\implies A_C[v] = x \oplus A_{C1}[u] as A_C[u]= A_{C1}[u]
\implies A_C[v] = A_{C2}[v] \oplus \big(A_{C2}[v]\oplus x \oplus A_{C1}[u]\big)
This means we need to apply the transformation of A_C[i] = A_{C2}[i] \oplus Y for all i in C2. Here Y=A_{C2}[v]\oplus x \oplus A_{C1}[u].
Time Complexity
In order to calculate this transformation we can directly iterate over the component C2 and modify the values. WLOG size of C2 \leq C1. Therefore in every merge operation we iterate over the smaller component and the size of the final component size(C1+C2) \geqslant 2 * size(C2).This means we can visit each node at max O(log N) times. The final complexity = O(N*logN + Q)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.