Editorial for Yet Another Contest 7 P4 - Paparazzi
Submitting an official solution before solving the problem yourself is a bannable offence.
Clearly, we can model the towns as a tree.
It suffices to naively simulate each operation, keeping track of every single paparazzo at all times. We can perform a BFS/DFS from to determine where each paparazzo moves.
At any point in time, the nodes occupied by the paparazzi form a subtree (a contiguous subgraph of the tree). We need to maintain which towns have at least one paparazzo. There are only three cases:
- is part of the subtree, but not one of its leaves. The effect is that all of the leaves are pruned. We can handle this by maintaining the degrees of each node in the subtree, and maintaining a set of leaves.
- is a leaf of the subtree. The effect is that all the leaves are pruned, except for .
- is outside the subtree. Let be the node in the subtree which is closest to . Let be the unique neighbour of which is closer to than . The effect is that node is added to the subtree, and then all leaves other than are pruned. In order to find and , pick any node in the subtree and consider the path from that node to the target node. One side of the path will be in the subtree, and the other side of the path will be outside of the subtree. and are the nodes where these two sides meet, so we can compute and using LCA and binary lifting.
Note that after each operation, at most one node is added to the subtree. Thus, the total number of times that a leaf is pruned across all operations cannot exceed .