Editorial for DMOPC '18 Contest 4 P5 - Dr. Henri and Wormholes
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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.
Time Complexity:
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
.
Time Complexity:
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
.
Therefore, .
The final answer is then the maximum value over all .
Time Complexity:
Comments