## Editorial for Wesley's Anger Contest 4 Problem 7 - Squirrel Cities

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: wleung_bvg

You may recognize similarities with the problem Enchanted Forest from the 2014 Chinese National Olympiad in Informatics.

For the first subtask, we can construct a graph for each query using only edges with and , and determining if the graph is connected. This can be done in many ways such as breadth first search, depth first search, or the Union-Find data structure.

Time Complexity: or

For the second subtask, we can make the observation that for each unique value of , there will be a minimum value of where the graph is completely connected. In fact, as decreases, the minimum value of decreases. In order to find this minimum value of for each , we need to find a minimum bottleneck spanning tree, which can be done by constructing a minimum spanning tree with all edges with a durability of at least , where the weight of each edge is . The minimum value of is equal to the maximum value of in the minimum spanning tree (assuming a tree exists). If the edges are presorted by , this can be done in time using Kruskal's algorithm. To answer the queries, we can binary search for the smallest value where and use the precomputed answer for that value. Alternatively, a two pointer approach can be used the answer the queries offline.

Time Complexity: