Editorial for DMOPC '23 Contest 1 P4 - Wandering Walk
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 .
Time Complexity:
Subtask 2
Let if is even and if is odd. With a similar observation to subtask 1, we note that if we start at vertex then there exists a walk that crosses each edge 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 .
Time Complexity:
Subtask 3
Let if is odd and if is even. Suppose the walk starts at vertex and ends at vertex , and we may assume without loss of generality (by reversing the walk if ). Then, before walking towards , we can first traverse each edge to the left of a total of times, stopping at the first edge where . A similar statement can be made for the edges to the right of . For each edge in between, we traverse them times. Given this, we can simply iterate over all pairs of and compute the relevant sum. To optimize this, we can use some precomputation in the form of prefix maximum arrays.
Time Complexity:
Subtask 4
Root the tree at vertex . We can define the following dynamic programming states:
- Let the length of the longest walk starting and ending at only traversing through edges in the subtree of .
- Let the length of the longest walk starting at only traversing through edges in the subtree of , ending at any vertex.
Note simply that for all children of with , where is the frequency value of the edge between and . This transition can be inspired by the observation from subtask 1.
Additionally, has a similar transition formula to , but we may choose any two children to contribute to the sum instead, since we can enter from one of these vertices and leave from the other. This can be inspired by the solution to subtask 2.
The longest walk starting at vertex is then . To compute the longest walk starting from any vertex, simply root the tree at every vertex and take the best of the answers.
Time Complexity:
Subtask 5
There are many ways to optimize the solution described in subtask 4 to . One possibility is to perform tree rerooting DP, where a second DFS through the tree recalculates the DP values for each root in total work. Another possibility is to define a third state the length of the longest walk passing through only traversing through edges in the subtree of . The transitions are no harder than the ones for and , and will be left as an exercise to the reader.
Time Complexity:
Comments