PROBLEM LINK:
Author: Misha Chorniy
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak
DIFFICULTY:
MEDIUM
PREREQUISITES:
Trees, Optimizations, XOR, LCA for easier subtasks
PROBLEM:
For a given tree of N nodes, where node v has assigned integer value Av, the goal is to calculate for each node w the maximal value of C(u, v), for any u and v in subtree of w, where C(u, v) is the XOR of all values of nodes at the path between u and v.
QUICK EXPLANATION:
For the full credit, compute the result from bottom of the tree to its root. For a single node v, calculate its value as the maximum value among its children and values combined from paths descending from v into different subtrees. While trying to maximize XOR’s of paths descending into one subtree of v with paths descending into other subtrees, always enumerate over paths in smaller of these two sets and for a fixed XOR value of one of the paths in it, try to find the value maximizing combined XOR in the larger set using any suitable data structure like for example a tree.
EXPLANATION:
In easier subtasks we will be using the fact that C(u, v) = C(r, u) XOR C(r, v) XOR ALCA(u, v) where r is the root of the tree and LCA(u, v) it is the Lowest common ancestor of nodes u and v. This fact is very handy, because for any two nodes u, v, we can compute C(u, v) knowing only values of C(r, w) for any w, which can be precomputed using DFS, and the ability of computing LCA of any two nodes. Solutions to easier subtasks are very similar, they all rely on iterating over all pairs of nodes v, u, computing C(u, v) as described above and actualizing the result of LCA(u, v) to the value of C(u, v) if it is greater than its current value. Notice that iterating over all possible pairs of nodes takes O(N2) time, so if LCA(u, v) can be found in time O(f(N)), then the total complexity of this kind of approach is bounded by O(N2 * f(N)).
Subtask 1
In the first subtask, N is at most 100, which is very small, so we can use LCA based method and find LCA(u, v) in linear time. This will result in O(N3) time complexity which is perfectly fine for the constraints here. LCA(u, v) can be easily find in linear time by just traversing from both u and v to the root of the tree and returning the first common node encountered at these paths.
Subtask 2
In the second subtask, N is at most 1000, so we need a faster method of computing LCA than in the first subtask. There is a famous and practical method running in O(log(N)) time with O(N * log(N)) precomputation time based on dynamic programming. Please refer here for more details about the method here.
Subtask 3
In the third subtask, N can be up to 104, which is not so easy to handle. However, O(1) LCA based approach should also be used here if its well optimized. This method is also covered in the article referred in the description of the second subtask.
Subtask 4
In the fourth subtask, N is at most 105 which makes any approach basing on iterating over all nodes unacceptable. We need a different approach here.
Let’s assume that we want to compute the result for node v. Notice, that it is either the result for any of its children, or a path from v descending from v to its one subtree combined with a path descending from v its to another subtree.
In the first case, the answer can be easily accumulated by just taking the maximum of answer of v’s children. The second case is more complicated.
Let assume that we are examining u, which is the ith children of v. Then, what we want to do, is to iterate over all XOR’s of paths descending from v to subtrees of children j < i and combine them with any of paths descending from v to the subtree rooted in u. The result will be the maximum value of XOR of among this combined paths with XOR of value Av.
However, the most straightforward iteration over all possibilities in unacceptable here, because if v has K children, then O(K2) values will be tested, which is way too many. Fortunately, a crucial optimization can be used here. Let A be the set of XOR values of all paths descending from v to subtrees of children j < i. Let B be the set of XOR values of all paths descending from v to u’s subtree. Now the goal is to find the values a ∈ A and b ∈ B, such that a XOR b XOR Av is maximum. This is equivalent to finding the best value a ∈ A, for which value a XOR c is maximized, where c = b XOR Av. Thus, if we iterate over all values b ∈ B, we reduced the problem to finding the element a ∈ A, which maximizes the value a XOR c. This problem can be solved for example by using Trie data structure for set A with depth equal the number of bits in the maximum element in A, which is at most 30 in this problem. More details about maximizing XOR are available here. However, this method if not optimized will also result in Time Limit Exceeded, because iterating over big sets B might be very costly. The crucial optimization is needed here. Notice, than if for sets A, B described above, we assure that we always iterate over elements in smaller of them, then any value will be examined at most log(N) times. This leads to total complexity of O(N * log(N) * log(max(X))), where X is the maximum possible result of any XOR operation (109 in this problem) . This is true, because each of N elements is iterated over at most log(N) while computing maximum XOR from both sets, and each such operation takes O(log(max(X)). For implementation details please refer to setter’s and tester’s solutions.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
