Editorial for UTS Open '15 #5 - Distribution Channel
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
The problem wants us to find the second-smallest spanning tree. To do so, we can first generate the minimum spanning tree (MST), keeping track of which edges were not used. We can then iterate over these unused edges, and use the cycle property of a minimum spanning tree: if there is a cycle, the heaviest edge will not be in the minimum spanning tree. To find the edge with the largest weight, we can use either HLD or a sparse table to query for the LCA is -1
if there are less than
Complexity:
Comments