Clearly, we can model the towns as a tree.

Subtask 1

It suffices to naively simulate each operation, keeping track of every single paparazzo at all times. We can perform a BFS/DFS from ~a_i~ to determine where each paparazzo moves.

Time complexity: ~\mathcal{O}(NM)~

Subtask 2

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:

• ~a_i~ 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.
• ~a_i~ is a leaf of the subtree. The effect is that all the leaves are pruned, except for ~a_i~.
• ~a_i~ is outside the subtree. Let ~X~ be the node in the subtree which is closest to ~a_i~. Let ~Y~ be the unique neighbour of ~X~ which is closer to ~a_i~ than ~X~. The effect is that node ~Y~ is added to the subtree, and then all leaves other than ~Y~ are pruned. In order to find ~X~ and ~Y~, 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. ~X~ and ~Y~ are the nodes where these two sides meet, so we can compute ~X~ and ~Y~ 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 ~N + M~.

Time complexity: ~\mathcal{O}((N+M)\log{N})~