Editorial for DMOPC '18 Contest 4 P5 - Dr. Henri and Wormholes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AvaLovelace

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: $\mathcal{O}(2^N)$ ~\mathcal{O}(2^N)~

For the second subtask, we can use a dynamic programming solution.

Root the tree at some node $r$ ~r~. We will find two values for each node $u$ ~u~:

$dp1[u]$ ~dp1[u]~: the length of the longest path starting and ending at $u$ ~u~, completely contained within the subtree rooted at $u$ ~u~.
$dp2[u]$ ~dp2[u]~: the length of the longest path starting in $r$ ~r~ and ending in $u$ ~u~.

To find $dp1[u]$ ~dp1[u]~, consider all children $v$ ~v~ of $u$ ~u~. If the edge $e$ ~e~ (of length $d$ ~d~) connecting $u$ ~u~ and $v$ ~v~ may be used twice, then we can go down to $v$ ~v~, traverse $dp1[v]$ ~dp1[v]~, then go back up to $u$ ~u~. Thus, $dp1[u] = \sum \begin{cases} 0 & twice(e) = 0 \\ dp1[v] + 2d & twice(e) = 1 \end{cases}$ .

To find $dp2[u]$ ~dp2[u]~, consider the parent $p$ ~p~ of $u$ ~u~. We can traverse $dp2[p]$ ~dp2[p]~, then traverse the $e$ ~e~ connecting $p$ ~p~ and $u$ ~u~, then traverse $dp1[u]$ ~dp1[u]~. However, if $e$ ~e~ may be used twice, $dp1[u] + 2d$ ~dp1[u] + 2d~ would already have been counted under $dp2[p]$ ~dp2[p]~, so we must subtract off this value. Thus, $dp2[u] = \begin{cases} dp2[p] + d + dp1[u] & twice(e) = 0 \\ dp2[p] - d & twice(e) = 1 \end{cases}$ .

The answer is then the maximum value over all $dp2[u]$ ~dp2[u]~ for all choices of $r$ ~r~, for a total complexity of $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~.

Time Complexity: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~

For the final subtask, we can expand on the solution for subtask 2.

Root the tree arbitrarily. Let $dp[u][c]$ ~dp[u][c]~ be the length of the longest path that runs through node $u$ ~u~ and is completely contained within the subtree rooted at $u$ ~u~. There are 3 possible cases $c$ ~c~:

$c = 0$ ~c = 0~: The path starts and ends in $u$ ~u~.
$c = 1$ ~c = 1~: The path starts in $u$ ~u~ and ends in some subtree of $u$ ~u~.
$c = 2$ ~c = 2~: The path starts and ends in two (not necessarily distinct) subtrees of $u$ ~u~.

Let $e$ ~e~ (of length $d$ ~d~) be the edge connecting a node $u$ ~u~ and its child $v$ ~v~. Let's consider the largest possible lengths of 3 cases of paths going through both $u$ ~u~ and $v$ ~v~:

Loop (starts and ends in $u$ ~u~): As described in the solution for subtask 2, if $e$ ~e~ may be used twice, we can start at $u$ ~u~, traverse $e$ ~e~, traverse $dp[v][0]$ ~dp[v][0]~, then traverse $e$ ~e~ again to return to $u$ ~u~. The length $len_L(v)$ ~len_L(v)~ of the longest loop through $v$ ~v~ would be $\begin{cases} 0 & twice(e) = 0 \\ dp[v][0] + 2d & twice(e) = 1 \end{cases}$ . Note that it is always optimal to loop through a child $v$ ~v~ if possible; if you consider any path through $u$ ~u~ that does not loop through $v$ ~v~, 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 $u$ ~u~ and ends in subtree $v$ ~v~): We can start at $u$ ~u~, traverse $e$ ~e~, then traverse either $dp[v][0]$ ~dp[v][0]~ or $dp[v][1]$ ~dp[v][1]~. The length $len_1(v)$ ~len_1(v)~ of the longest 1-loose-end through $v$ ~v~ would be $\max(dp[v][0], dp[v][1]) + d$ ~\max(dp[v][0], dp[v][1]) + d~.
2-loose-end (starts and ends in subtree $v$ ~v~): If $e$ ~e~ may be traversed twice, we can choose any of $dp[v][0]$ ~dp[v][0]~, $dp[v][1]$ ~dp[v][1]~, or $dp[v][2]$ ~dp[v][2]~, then add the path $v \to u \to v$ ~v \to u \to v~. The length $len_2(v)$ ~len_2(v)~ of the longest 2-loose-end through $v$ ~v~ would be $\begin{cases} 0 & twice(e) = 0 \\ \max(dp[v][0], dp[v][1], dp[v][2]) + 2d & twice(e) = 1 \end{cases}$ .

To find $dp[u][0]$ ~dp[u][0]~, notice that such a path must consist entirely of loops. Thus, $dp[u][0] = \sum len_L(v)$ ~dp[u][0] = \sum len_L(v)~ over all children $v$ ~v~ of $u$ ~u~.

To find $dp[u][1]$ ~dp[u][1]~, we can traverse the same path as $dp[u][0]$ ~dp[u][0]~, but must replace one of the loops with a 1-loose-end. Thus, to maximize $dp[u][1]$ ~dp[u][1]~, we must find the child of $u$ ~u~, $v_{max}$ ~v_{max}~, that has the greatest difference $len_1(v_{max}) - len_L(v_{max})$ ~len_1(v_{max}) - len_L(v_{max})~. Therefore, $dp[u][1] = dp[u][0] - len_L(v_{max}) + len_1(v_{max})$ .

To find $dp[u][2]$ ~dp[u][2]~, we can traverse the same path as $dp[u][0]$ ~dp[u][0]~, 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 $u$ ~u~, $v_{max1}$ ~v_{max1}~ and $v_{max2}$ ~v_{max2}~, that have the greatest differences $len_1(v_{max1}) - len_L(v_{max1})$ ~len_1(v_{max1}) - len_L(v_{max1})~ and $len_1(v_{max2}) - len_L(v_{max2})$ ~len_1(v_{max2}) - len_L(v_{max2})~. Thus, the length of the longest such path is $dp[u][0] - len_L(v_{max1}) + len_1(v_{max1}) - len_L(v_{max2}) + len_1(v_{max2})$ .
Replace one of the loops with a 2-loose-end. We must find the child $v_{max3}$ ~v_{max3}~ that has the greatest difference $len_2(v_{max3}) - len_L(v_{max3})$ ~len_2(v_{max3}) - len_L(v_{max3})~. Thus, the length of the longest such path is $dp[u][0] - len_L(v_{max3}) + len_2(v_{max3})$ .

Therefore, $dp[u][2] = \max \begin{cases} dp[u][0] - len_L(v_{max1}) + len_1(v_{max1}) - len_L(v_{max2}) + len_1(v_{max2})\\ dp[u][0] - len_L(v_{max3}) + len_2(v_{max3}) \end{cases}$ .

The final answer is then the maximum value over all $dp[u][c]$ ~dp[u][c]~.

Time Complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Comments

There are no comments at the moment.