PROBLEM LINK:
Author: Animesh Fatehpuria
Tester: Pushkar Mishra
Editorialist: Animesh Fatehpuria
DIFFICULTY:
Medium
PREREQUISITES:
Mo’s Algorithm, Segment Trees, Lowest Common Ancestor
PROBLEM:
You are given a Tree with N weighted nodes and you have to deal with two types of queries efficiently. The first query is to report the closest two values in a path between two nodes, and the second query is to report the farthest two values in a path between two nodes. There are total Q queries and N, Q \le 35000.
QUICK EXPLANATION
Linearize the tree by doing a dfs traversal of the tree. Note that we’ll do this a little differently to record the enter and exit time of each node i.e each node will appear twice in the linearized array. Now apply Mo’s Algorithm to sort the queries in a desired order. While expanding or contracting the window, we can check the number of times the node has been seen in this window and correspondingly add or subtract 1 in the particular position of the segment tree. The segment tree just needs to report the maximum difference between any two adjacent on values.
EXPLANATION
Note that for subtask 1 the solution is simple brute force.
For Subtask 2, we can build an lca like data structure precomputing 2^i ancestors of each node, and the maximum/minimum values in the path from each node to this ancestor. Then we can decompose each query (u, v) into u to lca(u, v) and v to lca(u, v) and compute the answer.
It is clear that type F queries can be easily handled.
For Type C queries, let us first look at a brute force solution.
First of all compress all the values stored at the nodes to a range of [1,N].
For each query of the form u,v do a dfs from node u and maintain a boolean array A such that A[i] = 1, if there exists a node having value i on the path from u to current node. On reaching the node v during dfs, the boolean array would represent what all values are present on the path from u to v. Now we can just iterate over the boolean array and for every consecutive i, j such that A[i] and A[j] are both 1, we can keep min of (j - i).
We can fasten up the above solution by maintaining the boolean array A using segment tree. We could use the operations set/unset an element using point update of 1/0 and range max of difference of consecutive set elements. This can easily be done by maintaining the leftmost and rightmost set element in the range of each node.
Now, let’s try to imagine that the queries are on subarrays and not tree-paths. Let us first do a dfs ordering of the given tree (rooted at any arbitrary node) such that each node comes twice in the array, once while entering the dfs and other while exiting the dfs. Now, a path from u to v can be represented as consecutive elements in this array. More on this here.
Hence, if we can implement a function to add a value to a range and a function to remove a value from a range, along with maintaining the answer of the current range, we can easily use MO’s algorithm to solve the problem. To implement the add and remove functions, we could use the segment tree idea described above in the brute force approach. Hence we could use a segment tree along with MO’s algorithm to solve the problem.
Final Complexity: O(Q\sqrt{N}\log{N})
Note : The constraints were such that some brute force solutions passed during the contest, although we had done some testing to ensure that it doesn’t. We had no option but to make the TL very strict, at 3.5 seconds, in order to cut out the brute force solutions. Note that solutions using sets might not pass, as sets and multisets have a large constant factor. We deeply regret any inconvenience caused.
