Editorial for DMOPC '18 Contest 4 P5 - Dr. Henri and Wormholes
Submitting an official solution before solving the problem yourself is a bannable offence.
This problem asks for the longest possibly non-simple path through a tree, where some edges may be traversed at most twice and the rest at most once.
For the first subtask, we can write a brute-force backtracking solution to check all possible paths.
For the second subtask, we can use a dynamic programming solution.
Root the tree at some node . We will find two values for each node :
- : the length of the longest path starting and ending at , completely contained within the subtree rooted at .
- : the length of the longest path starting in and ending in .
To find , consider all children of . If the edge (of length ) connecting and may be used twice, then we can go down to , traverse , then go back up to . Thus, .
To find , consider the parent of . We can traverse , then traverse the connecting and , then traverse . However, if may be used twice, would already have been counted under , so we must subtract off this value. Thus, .
The answer is then the maximum value over all for all choices of , for a total complexity of .
For the final subtask, we can expand on the solution for subtask 2.
Root the tree arbitrarily. Let be the length of the longest path that runs through node and is completely contained within the subtree rooted at . There are 3 possible cases :
- : The path starts and ends in .
- : The path starts in and ends in some subtree of .
- : The path starts and ends in two (not necessarily distinct) subtrees of .
Let (of length ) be the edge connecting a node and its child . Let's consider the largest possible lengths of 3 cases of paths going through both and :
- Loop (starts and ends in ): As described in the solution for subtask 2, if may be used twice, we can start at , traverse , traverse , then traverse again to return to . The length of the longest loop through would be . Note that it is always optimal to loop through a child if possible; if you consider any path through that does not loop through , adding such a loop will never decrease the path's length and will not affect the rest of the path.
- 1-loose-end (starts in and ends in subtree ): We can start at , traverse , then traverse either or . The length of the longest 1-loose-end through would be .
- 2-loose-end (starts and ends in subtree ): If may be traversed twice, we can choose any of , , or , then add the path . The length of the longest 2-loose-end through would be .
To find , notice that such a path must consist entirely of loops. Thus, over all children of .
To find , we can traverse the same path as , but must replace one of the loops with a 1-loose-end. Thus, to maximize , we must find the child of , , that has the greatest difference . Therefore, .
To find , we can traverse the same path as , but must do one of the following:
- Replace two of the loops with two 1-loose-ends. We must find the two distinct children of , and , that have the greatest differences and . Thus, the length of the longest such path is .
- Replace one of the loops with a 2-loose-end. We must find the child that has the greatest difference . Thus, the length of the longest such path is .
The final answer is then the maximum value over all .