Subtask 1

Simply try every possible path, and check each of the fireplaces below at every move.

Time Complexity: ~\mathcal{O}(CN^2)~

Subtask 2

The same as subtask 1 but a bit bigger, there is no special trick for only fixing once.

Subtask 3

Take all the fireplaces and store them as a pair of <# of parents, index>. Sort by the number of parent fireplaces from greatest to least. This lists the possible paths from best to worst. During each update, check if the best path is still traversable. If it is, print it; otherwise move on to the next best path and check again. You can use algorithms such as HLD to reduce the time required to check each path.

Time Complexity: ~\mathcal{O}((N+C) \log N)~

This can also just be solved with a more optimized brute force.

Subtask 4

Realize that the entire tree is now laid out as a path, which can just be treated as an array containing each fireplace's distance to the chimney. During each update, simply take the lowest delay of all the grapple guns and binary search for the first fireplace where Santa would have to stop.

Time Complexity: ~\mathcal{O}((N+C) \log N)~

Full Solution

We can view the grapple guns placed at the fireplaces as blocking off certain routes for Santa. To determine what range of nodes each grapple gun blocks off, we must look at 2 things: its delay and the path to the chimney.

For simplicity, we will refer to the distance from a fireplace to the chimney as its "depth".

One case is that the depth is lower than its delay. This means Santa can get to the fireplace and continue his route before the grapple gun fires, so we ignore any grapple guns for which this is the case.

Otherwise, we search for the highest fireplaces whose depth is no less than the delay. If the depth is greater than the delay, Santa cannot reach the fireplace before it fires, and the route is effectively blocked off. The situation where the depth is equal to the delay is stated in the problem statement, and is again blocked off.

Once we find out the highest fireplace that is blocked off, we need to use a segment tree to range update the area blocked off. Before we can have a range update segment tree though, we need to index the nodes in the Euler tour order with a simple DFS. Now to find the answers, we have a multiset in each node of the segment tree that stores blocked off values. If a node's multiset has a value, then it is blocked off and its children are irrelevant. We take the lowest value in the multiset as the answer. If the multiset is empty, we take the answer of the node's children. After each update, the answer will be stored at the very top node.

Time Complexity: ~\mathcal{O}(C \log^2 N)~