Editorial for WC '16 Contest 3 S4 - Replay Value


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.

The graph formed by the towns and routes forms a tree structure. Upon rooting the tree at an arbitrary node (such as node 1), this problem can be solved with dynamic programming. For each node i, let Up[i] be the number of different non-decreasing paths contained within i's subtree and ending at i, and similarly let Down[i] be the number of different non-increasing paths contained within i's subtree and ending at i. Paths of length 0 (spanning only 1 node) are included.

Let's consider how to compute these Up and Down values for each node i. Firstly, we can set Up[i] = Down[i] = 1 to include the path starting and ending at i (which is both non-decreasing and non-increasing). Next, consider each of i's children c which paths might be coming from. If D[i] > D[c], then all paths coming from c into i must non-decreasing, meaning that we can increment Up[i] by Up[c]. Similarly, if D[i] < D[c], then we can increment Down[i] by Down[c]. Finally, if D[i] = D[c], then both types of paths may occur, so we should both increment Up[i] by Up[c], and increment Down[i] by Down[c]. Note that node i's Up and Down values only depend on those of its children, meaning that we can perform these computations recursively and populate these arrays for all nodes in \mathcal O(N) time.

What remains is computing the actual answer based on these Up and Down values. For each node i, let's consider how many paths are contained within i's subtree and include i itself (in other words, paths which have i as their "topmost" node). If we can determine this value for every node, and add these N values together for all nodes, then every valid path will be counted exactly once. For the most part, this value for node i is simply Up[i] \times Down[i]. 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 i, as the starting town is required to be different than the destination town, so we should subtract 1 for that. Aside from that, for each child c such that D[i] = D[c], this approach will include paths which come up from c to i, and then back down to c, which are also disallowed. As such, for each such child, we should simply subtract Up[c] \times Down[c] from the answer. These computations to tally up the total answer can be done during the dynamic programming process in an additional \mathcal O(N) time.


Comments

There are no comments at the moment.