Author: kamal1998
Tester: cypher101
Editorialist: kamal1998
DIFFICULTY
EASY-MEDIUM
PREREQUISITES
DFS, BFS, TREES, SEGMENT TREES, CENTROID DECOMPOSITION
PROBLEM:
You are given a tree with all the nodes initially unmarked. You will be given two types of queries one of type 0 u meaning mark or unmark node u and other of type query is 1 u that is to tell the distance to the nearest marked node from u if none print -1.
QUICK EXPLANATION:
As you can see the problem can be solved using segment trees and HLD (Heavy Light Decomposition) which will be a bit long and complex but if one notices properly we can see that we can apply another divide and conquer approach which is Centroid Decompositon to solve the problem. By breaking the trees into different subtrees we can then store the distance of any marked node from the centroid, then we can calculate the answer easily. But the time limit is 2s which gives room for more easy solution to pass such as doing the whole bfs traversal and finding the node with the least distance.
EXPLANATION:
For those who are new to the concept of Centroid Decompositon you can more about it here or here. You must also know the basics of Segment Trees. The problem is just basic implementation of centroid decomposition, the main gesture behind the solution is that you have to decompose the tree into many subtrees and for each subtree you have to calculate the minimum distance of a marked node from the centroid residing in the subtree.
Now in the implementation first you must calculate the size of the subtree rooted at each node, this can be done using dfs. Then you can decompose the tree and store the distance of each node from the centroid of their respective subtree rooted at that centroid. For each query of type 0 u you have to store the distance of u from all the centroids (while marking) or remove it while unmarking. For each query of type 1 u you just have to check all the centroids and for each centroid the minimum distance to the nearest marked node. That is, distance = min(distance, distance of u from centroid+distance of marked node from centroid).
ALTERNATE EXPLANATION:
The time limit of the problem even gives room for more naive approaches and so the problem can be solved by using a simple bfs traversal to find the nearest marked node.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s/Editorialist solution can be found here