a codeforces contest.
D. Boxed Like a Fish
let a “good node” denote a node which wins when the timer is currently at . we make two observations:
- every leaf is, by definition, a good node.
- if the path between two good nodes has distance , all nodes on that path are also good nodes.
for 2, we can see that this condition is definitely sufficient. let the path be from to , and any intermediate node be . then, we can start moving from to , and if at any point we are cut off, we can just reverse direction and start moving to .
it’s a little more difficult to show that by iterating 2, we’ll eventually have found all good nodes. let’s consider each connected component of bad nodes. all leaves of this component must have distance from one another, otherwise some of these nodes would not be bad. therefore, if we start from any node in the component, the adversary can just repeatedly cut us off as soon as we hit a leaf, thus trapping us within this component forever.
it remains to figure out how to efficiently iterate this process. a helpful observation is that we can always perform operation 2 in a way such that no nodes that were already marked good are marked again. they will thus look tree-like, something like:
now we root the tree at and compute for each subtree, the minimum depth of a good node given that operation 2 is applied only within that subtree.