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.

Authors: 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)

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

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

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

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

To find dp2[u], consider the parent p of u. We can traverse dp2[p], then traverse the e connecting p and u, then traverse dp1[u]. However, if e may be used twice, dp1[u] + 2d would already have been counted under 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] for all choices of r, for a total complexity of \mathcal{O}(N^2).

Time Complexity: \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] be the length of the longest path that runs through node u and is completely contained within the subtree rooted at u. There are 3 possible cases c:

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

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

  1. Loop (starts and ends in u): As described in the solution for subtask 2, if e may be used twice, we can start at u, traverse e, traverse dp[v][0], then traverse e again to return to u. The length len_L(v) of the longest loop through 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 if possible; if you consider any path through u that does not loop through v, adding such a loop will never decrease the path's length and will not affect the rest of the path.
  2. 1-loose-end (starts in u and ends in subtree v): We can start at u, traverse e, then traverse either dp[v][0] or dp[v][1]. The length len_1(v) of the longest 1-loose-end through v would be \max(dp[v][0], dp[v][1]) + d.
  3. 2-loose-end (starts and ends in subtree v): If e may be traversed twice, we can choose any of dp[v][0], dp[v][1], or dp[v][2], then add the path v \rightarrow u \rightarrow v. The length len_2(v) of the longest 2-loose-end through 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], notice that such a path must consist entirely of loops. Thus, dp[u][0] = \sum len_L(v) over all children v of u.

To find dp[u][1], we can traverse the same path as dp[u][0], but must replace one of the loops with a 1-loose-end. Thus, to maximize dp[u][1], we must find the child of u, v_{max}, that has the greatest difference 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], we can traverse the same path as dp[u][0], but must do one of the following:

  1. Replace two of the loops with two 1-loose-ends. We must find the two distinct children of u, v_{max1} and v_{max2}, that have the greatest differences len_1(v_{max1}) - len_L(v_{max1}) and 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}).
  2. Replace one of the loops with a 2-loose-end. We must find the child v_{max3} that has the greatest difference 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].

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.