Editorial for DMOPC '23 Contest 1 P4 - Wandering Walk


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: 4fecta

Subtask 1

Note that there exists a Eulerian circuit (treating all edges as multi-edges) of the entire tree since all vertices have even degree. Thus, the answer is simply \sum c_i.

Time Complexity: \mathcal{O}(N)

Subtask 2

Let E(x) = x if x is even and E(x) = x-1 if x is odd. With a similar observation to subtask 1, we note that if we start at vertex 1 then there exists a walk that crosses each edge E(c_i) times. Furthermore, we may improve upon this walk by walking along an odd edge once more in the end, and similarly in the beginning. Thus, the answer is simply \sum E(c_i) + \min(2, \text{# of odd edges}).

Time Complexity: \mathcal{O}(N)

Subtask 3

Let O(x) = x if x is odd and O(x) = x-1 if x is even. Suppose the walk starts at vertex l and ends at vertex r, and we may assume l \le r without loss of generality (by reversing the walk if l > r). Then, before walking towards r, we can first traverse each edge to the left of l a total of E(c_i) times, stopping at the first edge where c_i = 1. A similar statement can be made for the edges to the right of r. For each edge in between, we traverse them O(c_i) times. Given this, we can simply iterate over all pairs of (l, r) and compute the relevant sum. To optimize this, we can use some precomputation in the form of prefix maximum arrays.

Time Complexity: \mathcal{O}(N)

Subtask 4

Root the tree at vertex 1. We can define the following dynamic programming states:

  • Let dp[u][0] := the length of the longest walk starting and ending at u only traversing through edges in the subtree of u.
  • Let dp[u][1] := the length of the longest walk starting at u only traversing through edges in the subtree of u, ending at any vertex.

Note simply that dp[u][0] = \sum_v \,(dp[v][0] + E(c)) for all children v of u with c \geq 2, where c is the frequency value of the edge between u and v. This transition can be inspired by the observation from subtask 1.

Additionally, dp[u][1] has a similar transition formula to dp[u][0], but we may choose any two children v to contribute \max(dp[v][0], dp[v][1]) + O(c)) to the sum instead, since we can enter u from one of these vertices and leave u from the other. This can be inspired by the solution to subtask 2.

The longest walk starting at vertex 1 is then \max(dp[1][0], dp[1][1]). To compute the longest walk starting from any vertex, simply root the tree at every vertex and take the best of the N answers.

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

Subtask 5

There are many ways to optimize the solution described in subtask 4 to \mathcal{O}(N). One possibility is to perform tree rerooting DP, where a second DFS through the tree recalculates the DP values for each root in \mathcal{O}(N) total work. Another possibility is to define a third state dp[u][2] := the length of the longest walk passing through u only traversing through edges in the subtree of u. The transitions are no harder than the ones for dp[u][0] and dp[u][1], and will be left as an exercise to the reader.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.