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

Remember to use this editorial 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: AQT

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.

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.

def fun(int curSegTreeNode)
curSegTreeNode's sum is the sum of its left child's range and right child's range