Problem Link - Pillars
Problem Statement
In the middle of a certain ocean, there are n pillars rising high out of the waters. These pillars are connected by an ancient network of n-1 bridges, each at a height of 10^9 above sea level. It is possible to travel between any pair of pillars using these bridges, that is, the pillars are \textit{connected} through the ancient bridges.
At the current time, there are a total of m bridges. This is because, in the modern era, the inhabitants of these pillars have built m-(n-1) additional ad hoc bridges to increase the convenience of travel. However, due to the technological decline, each of these ad hoc bridges only has a height of between 0 and 5 \cdot 10^8 above sea level.
The inhabitants want their pillars to be \textit{biconnected}: that is, the pillars should be connected even if any one bridge breaks down. However, they know that the seas may rise in the future, rendering bridges with height strictly below this new water level useless. Determine the maximum water level at which the pillars are still biconnected.
Additionally, the inhabitants plan to build q more bridges in the future in an order 1, 2 \dots q. Similarly to the ad hoc bridges, each of these bridges have a height of between 0 and 5 \cdot 10^8 above sea level. After each additional bridge, report the new maximum water level at which all the pillars are still biconnected.
Approach
To solve the problem, we need to ensure the graph formed by the pillars and bridges remains biconnected even if any single bridge fails. This can be modeled using graph, specifically identifying bridges (edges) that keep the graph connected.
We will use Heavy-Light Decomposition to break the tree into chains and a Segment Tree with Lazy Propagation to maintain and query the maximum water level that keeps the graph biconnected.
First, we perform DFS to decompose the tree and identify heavy edges. We use the segment tree to update the water level for each bridge and query the current maximum water level that still ensures biconnectivity.
For each query, we add the new bridge and update the segment tree to reflect the new maximum level that keeps the graph biconnected.
Time complexity
The time complexity is O((n + m) log n), as each update and query operation takes logarithmic time, with a total of n + m operations.
Space complexity
The space complexity is O(n), due to the storage required for the graph and segment tree.