## Editorial for CCO '23 P5 - Travelling Trader

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: zhouzixiang2004

The three possible values of are very different problems. We will present their solutions in the order as this is roughly the increasing order of difficulty.

#### Subtask 1:

When , the answer is the longest node-weighted path from the root, which can be found in a single DFS.

#### Subtasks 5, 6:

When , it turns out that it is always possible to visit all nodes. We can do this recursively using the state , which starts from a node , traverses every node in the subtree of once, and ends at a child of (or itself if the subtree consists of just ). If are the children of , represents the path formed by , where denotes reversing the path.

Reconstructing the path naively (copying around and reversing parts of the path) takes time and only passes subtask 5. It is possible to use small to large merging of double-ended queues to solve subtask 6 in time. We can also reconstruct the path in linear time by instead building up a second graph structure representing parts of the path, only passing around the endpoints of the partial path during the reconstruction DFS, and doing a path traversal afterwards to print the path in the correct order.

Note that this solution would also solve all of if such were permitted.

#### Subtasks 2, 3, 4:

When , we need to use dynamic programming to find the optimal path. The following solution may be found by very carefully analyzing all possible ways the path may go. After writing some dynamic programming code to calculate the answer, it is recommended to write a brute force solution and compare answers with it on many random tests before trying to write the path reconstruction code, as it is very easy to miss a case in this problem.

Let represent the best path starting at and staying within the subtree of . Let represent the best path starting at , staying within the subtree of , and ending at a child of or just . Let represent the best path starting at a child of and staying within the subtree of (or just ). Let be the children of . The transitions are of the form:

• , representing the path
• , representing the path
• , representing the path
• , representing the path
• , representing the path

and similar ones for other orderings of the children.

These transitions mostly just add up , except up to of the children are replaced with a dp value. For subtask 2, it suffices to loop over all ways to choose these up to special children for a time complexity of . For subtasks 3 and 4, we can instead maintain the children with the maximum and only consider these to compute the dp values in time. Reconstructing the path in time naively suffices for subtask 3, and for subtask 4, an or time reconstruction is needed, which can be done similar to the case.

## Comments

There are no comments at the moment.