PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Animesh Fatehpuria
Second Tester: Kevin Atienza
Editorialist: Pawel Kacprzak
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Trees, LCA
PROBLEM:
In this problem, for a given tree of N nodes the task is to handle Q queries. Each query consists of two vertices t and j denoting the initially positions of respectively Tom and Jerry in the tree. In one second, both Tom and Jerry can and have to change their current positions to one of the adjacent nodes to nodes they are currently in, and Jerry makes the move first, which is followed by Tom’s move. The answer for a single query is the minimum number of seconds Tom needs to catch Jerry, i.e. be in the same vertex as he is no matter how Jerry moves.
QUICK EXPLANATION:
For each query, find the middle of the path from t to j. Let’s call this node v. Then find the maximum distance from v to it’s subtree where j is also located. The final answer is the sum of this distance and the distance from t to v.
EXPLANATION:
Notice that if v is the node exactly in the middle of the path from t to j, then Tom can always prevent Jerry from crossing v by just moving greedily towards v. Thus the best Jerry can do is to find the longest path from $v$’s located in the same subtree of v that j is in. This observation is crucial and needed to came up with the solution. Exact solution and its time complexity depends on how does one implement these two parts, i.e. finding the middle vertex and the finding the longest path in one of its subtrees. Various approaches can be used to solve each subtask and they are described below. Last but not least thing to mention is that computing the middle vertex can be sometimes tricky, and when implementing it one should for example remember than in each turn Jerry makes his move first.
Subtask 1
In the first subtask we have bot N, Q \leq 100. This allows us to make a straightforward simulation of the whole process independently for each query. More specifically, for a single query, we can first find the middle vertex v by performing for example dfs from t and after finding it, compute the maximum distance from v into any vertex in v’s subtree where also j is located, which can be also done using dfs.
Subtask 2
In this subtask, in each query, node j is fixed. This allows us to precompute for all nodes u the middle node on path from j to u using a single dfs from j beforehand. Moreover, for each node u, the longest path from u descending into its subtree where j is also located can be computed similarly also beforehand. This allows us to answer each possible query offline using these precomputed informations.
Subtask 3
In this subtask, in each query, node t is fixed, so the problem is very similar to the one in the second subtask and the approach follows also the same idea, but has to be implemented independently of the solution for the second subtask, because slightly different informations have to be precomputed.
Subtask 4
In this subtask we know that N \leq 5000 and besides that all original constraints are preserved. At least a few possible approaches can take advantage of this fact and one of them is to first compute middle nodes for all possible pairs of nodes t and j, which can be computed for example by using dfs from each possible node t in order to compute middle nodes from t to all other nodes, and then use dynamic programming to compute dp[v][u] as the length of the longest path starting from v and descending into subtree of v where u is located. Then, all queries can be answered offline by using both these look-up tables to locate the middle node first, and then computing longest paths from this middle node descending into subtree where j is located. The total time complexity of this method is (N^2 + Q) for a single test case.
Subtask 5
In the last subtask, we can have up to 10^5 nodes and queries, which makes the problem significantly harder than it is in any of the earlier subtasks. However, remember that the same general rule for solving the problem applies, and it just has to be implemented more efficiently. Just to recall, the strategy is to solve each query (t, j) independently, by first finding the middle node v in the path from t to j and then compute the most distant node from v located in the same subtree of v that j is located in.
The first part, finding the middle node, can be solved using [LCA][22222] algorithm. The idea is that finding L = LCA(t, j) allows us to find the length of the path between t and j, which can be used to find the middle node when it’s combine with the function getKthAncestor(u,k) returning the k-th ancestor of u. This function can be implemented using, so-called jumps table which is also used to compute LCA of two nodes. For implementation details please refer to setter and both testers solutions listed below, or this [TopCoder article on how to compute LCA efficiently][11111].
The second part, i.e. the maximum distance from v to any node located in the same subtree of v that j is also located can be computed in a several ways. One possibility is to use to precompute for each edge (v, u) in the tree, the maximum distance from v to its subtree rooted in u. This can be easily done by running dfs with memoization. Notice that there are at most 2 \cdot N possible edges, resulting in the same number of entries in a look-up table they produce. This look-up table can be used to compute the final result as soon as the middle node is found. Exactly this approach was used by one of the testers for the problem. For other implementations you please refer to setter and second tester solutions listed below.
In summary, a single test case for this subtask can be solved in O(N \cdot \log(N) + Q \cdot \log(N)) time, and it is dominated by the time needed to compute LCA.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
Second Tester’s solution can be found here.
[11111]: https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Another%20easy%20solution%20in%20O(N%20logN,%20O(logN)
[22222]: https://en.wikipedia.org/wiki/Lowest_common_ancestor
