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)~