Editorial for Tree of Life
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, the longest common substring of two DNA sequences is simply the minimum of their lengths. Note that two nodes ~A~ and ~B~ are distant if and only if there is a node with two distinct children such that ~A~ is in the subtree of one of the children and ~B~ is in the subtree of the other. We can use simple tree DP to determine the answer.
Time Complexity: ~\mathcal O(N)~
For the second subtask, there were several different solutions. The majority of them were based around binary searching for the answer. This editorial will outline a different approach.
Consider the suffix array of the concatenation of the ~N~ strings. We use the following algorithm:
Keep a left pointer and a right pointer. There are two states: either the left pointer is fixed or the right pointer is fixed. Initially, the left pointer is fixed.
When the left pointer is fixed, keep moving the right pointer until the node corresponding to the suffix at the right pointer is not an ancestor of the node corresponding to the suffix at the left pointer. Once this happens, the right pointer is now fixed.
When the right pointer is fixed, keep moving the left pointer until it reaches the right pointer. Once this happens, the left pointer is now fixed.
Throughout these steps, check whether or not the two nodes being pointed at are distant and compute the LCP of the two suffixes being considered. This algorithm is guaranteed to find the answer. The proof of this is left to the reader.
Time Complexity: ~\mathcal O(S+N \log N)~