Editorial for WC '16 Contest 3 S4 - Replay Value
Submitting an official solution before solving the problem yourself is a bannable offence.
The graph formed by the towns and routes forms a tree structure. Upon rooting the tree at an arbitrary node (such as node ), this problem can be solved with dynamic programming. For each node , let be the number of different non-decreasing paths contained within 's subtree and ending at , and similarly let be the number of different non-increasing paths contained within 's subtree and ending at . Paths of length (spanning only node) are included.
Let's consider how to compute these and values for each node . Firstly, we can set to include the path starting and ending at (which is both non-decreasing and non-increasing). Next, consider each of 's children which paths might be coming from. If , then all paths coming from into must non-decreasing, meaning that we can increment by . Similarly, if , then we can increment by . Finally, if , then both types of paths may occur, so we should both increment by , and increment by . Note that node 's and values only depend on those of its children, meaning that we can perform these computations recursively and populate these arrays for all nodes in time.
What remains is computing the actual answer based on these and values. For each node , let's consider how many paths are contained within 's subtree and include itself (in other words, paths which have as their "topmost" node). If we can determine this value for every node, and add these values together for all nodes, then every valid path will be counted exactly once. For the most part, this value for node is simply . However, some invalid paths also end up being counted in this fashion, which must then be subtracted. One such path is the path which starts and ends at , as the starting town is required to be different than the destination town, so we should subtract for that. Aside from that, for each child such that , this approach will include paths which come up from to , and then back down to , which are also disallowed. As such, for each such child, we should simply subtract from the answer. These computations to tally up the total answer can be done during the dynamic programming process in an additional time.
Comments