Basics
First, consider how we might solve the problem if . Actually, if we let denote the distance between nodes and , it turns out the following algorithm works:
In order of increasing and while we have not exceeded the threshold, set the closing time of node to be .
Proof. We can use a bounding argument.
- If we want nodes to be reachable from , then the closing times of each of these nodes must be at least ; therefore, the answer is lower-bounded by the sum of the smallest .
- At the same time, our construction guarantees that all nodes can be visited. Roughly, this is because if we select all nodes with for some threshold , there necessarily exists a path using only these nodes to any node with (by definition of distance).
(note that this approach for should apply to general graphs as well, not just trees)
An illustration of this strategy. The red numbers represent for each node, and the shaded nodes are the ones for which we set the closing times to . All other closing times are .
Subtask 1
Now, let’s consider the first subtask in which the distance between and is greater than . This means that no node can be reachable from both and , which means we can essentially reuse our solution for ! In particular:
- Let .
- Like before, sort by and take until we can’t.
The proof of correctness is essentially the same as in the case.
Again, red numbers represent cost and shaded nodes are the reachable ones. In this scenario, the best answer is therefore .
Line
Now, consider the case in which the tree is a single line, and and are at its ends (but the distance between them can now be less than ). Now, a node could be reachable from both and as long as its closing time is at least . Thus, we now have to decide for each node whether its reachable zero times, once, or twice (corresponding to costs , , and respectively).
A possible solution. The square means we want this node to be reachable from both and , and the blue costs represent . Therefore, the total cost of this configuration is . The total convenience is 1 + 1 + 2 + 1 + 1 = 6.
First, note that in order for any node to be a square, all nodes on this line must at least be shaded circles first (some of which we can then “upgrade” to squares). Moreover, the nodes upgraded to squares must start from the midpoints and propagate outward. For instance, in the example above, it’d be invalid to have only the second node from the left as a square, and the rest as circles.
The midpoints are circled in green (lengths are the same as in the above image). Note that if the second-from-left node is a square, the third-from-left node must also be a square. Therefore, the configuration shown here is invalid.
However, just like before, it turns out that any optimal configuration is actually valid!
Proof. Consider the cost of upgrading each node, . Plotting, it should look something like this:
The cost will decrease until the first midpoint, then increase after the second midpoint (costs are shown above the graph in black, and the order of upgrades is indicated by the green numbers). Therefore, upgrades always radiate outward from the center, which corresponds to a valid solution.
Thus, our final algorithm is as follows:
- First, upgrade nodes to shaded circles in order of increasing while we still can.
- If any nodes remain unshaded, terminate.
- Otherwise, upgrade circles to squares in order of increasing .
The final answer is .
Tree
To generalize our line solution, we claim the following solution works for any tree:
- First, find the answer under the assumption that no node is reachable twice (this is the Subtask 1 solution).
- Otherwise, assume some node is reachable twice: this means that all nodes on the path from to must be upgraded at least once.
- From here, make any additional upgrades: we claim that any choice of upgrades that minimizes total cost necessarily corresponds to a valid solution.
If the claim in point 3 is true (which we will prove momentarily), the problem reduces to the following:
You are presented with boxes. From box you can take zero items for cost 0, one item for cost , and two items for cost . it is guaranteed . Find the maximum number of items that can be taken given that the total cost must not exceeded .
To solve this, we can split boxes into two types:
-
. We can split this box into two single-item boxes with cost and respectively. Note that we should never take the second box without taking the first box, so any valid solution with this reduction corresponds to a valid solution for the original problem as well.
-
. Note that if we take two half-boxes of this type, it’s always better to instead take the entire box with smaller .
Two half-boxes. A lower-cost solution can be achieved by making the swap indicated by the blue arrow.Therefore, we will take at most one half-box of this type, and the remaining full boxes should then be taken in order of increasing . So, sorting these boxes by , we will always take a prefix with the exception of at most one element (which should be the element with maximum or some later element with minimal ).
So, we can just enumerate all prefixes of type 2 boxes, as well as whether we choose one of these boxes to be a half-box, then find the maximum number of type 1 boxes (which have been reduced to single item-boxes) we can take afterward. This can all be done in .
Proof of claim. We wish to show that the optimal solution found by the above algorithm (which relaxes the original problem constraints) actually always corresponds to a valid solution under the original constraints as well.
First, let be the set of nodes upgraded any number of times in an optimal solution.
Lemma. If the solution is optimal, then will be connected.
Proof. Recall that all nodes on the path from to are necessarily part of . For other nodes in , if its parent (when the tree is rooted at ) is not in , it cannot be worse to replace this node with its parent.
If is not connected, the blue move cannot increase cost.
Now, we just need to show that the selection of squares in an optimal solution leads to a valid configuration as well. This can be shown as follows:
- First, decide and upgrade all nodes in to circles.
- Then, additionally upgrade some of these nodes to squares in increasing order of .
The key thing to note here is that within each subtree hanging off the path from to , the value of is constant.
Each subtree is shown with the upgrade cost corresponding to every node in that subtree.
Therefore, just as before, our upgrades will radiate from the center subtree outward. Furthermore, because upgrade cost is constant within a subtree, we can always upgrade in a way such that shallower nodes are upgraded first. It can be shown that these conditions will always result in a valid solution.