Subtask 1

For each query ~q~, we can think of it as cutting all edges that connect nodes of distance 1 from ~n_q~ and nodes of distance 2 from ~n_q~ from time ~a_q~ to ~b_q~ inclusive. So for each query, we can perform a BFS and maintain an integer array that represents for each edge, how many quarantines will have the edge cut. The answer is the number of components which is the number of edges cut + 1, from Euler's Formula or the fact that all edges are bridges in a tree.

Subtask 2

Root the tree arbitrarily and consider the BFS ordering of it. For a node ~n~, all nodes in ~n~'s subtree that have a distance of ~k~ form a consecutive range in the BFS ordering. Map each edge to the node that is furthest away from its root. So, every query consists of 4 consecutive ranges of nodes; nodes in subtree of ~n~ that are 2 away, nodes in subtree of ~n~'s parent that are 1 away and appear before ~n~, nodes in subtree of ~n~'s parent that are 1 away and appear after ~n~ and ~n~'s parent.

To find such ranges we can precompute them after performing a BFS and maintain the first time we see a node that is ~k~ away in ~n~'s subtree. To perform the queries, there are multiple methods. One way is to use Square Root Blocking, where we would turn off individual elements and their blocks. Another method is to use Divide and Conquer on time with a BBST of edges. The two algorithms run in ~\mathcal O(N \sqrt N)~ and ~\mathcal O(N \log^2 N)~ respectively.

Subtask 3

For this subtask, we can use a Segment Tree of edges where each node of the Segment Tree stores whether or not all the nodes are covered by a range and how many edges have not been cut yet. The pseudocode is the push up function for the Segment Tree. For each query ~q~, we would increment before outputting for time ~a_q~ and decrement after outputting for time ~b_q~ the respective ranges. This solves the problem in ~\mathcal O(N \log N)~ time.

def fun(int curSegTreeNode)
    if range is fully covered by 1 node
        curSegTreeNode's sum is its range
    otherwise
        curSegTreeNode's sum is the sum of its left child's range and right child's range