## Editorial for CPC '21 Contest 1 P7 - AQT and Quarantine

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

#### Subtask 1

For each query , we can think of it as cutting all edges that connect nodes of distance 1 from and nodes of distance 2 from from time to 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 , all nodes in 's subtree that have a distance of 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 that are 2 away, nodes in subtree of 's parent that are 1 away and appear before , nodes in subtree of 's parent that are 1 away and appear after and '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 away in '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 and 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 , we would increment before outputting for time and decrement after outputting for time the respective ranges. This solves the problem in 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
```

## Comments