聲明：本題目是LibreOJ 136. 最小瓶頸路 題解 最小生成樹 倍增加強版，建議先學習簡單版的做法。
題目鏈接：LibreOJ 137. 最小瓶頸路（加強版）
題目描述：

給定一張無向圖，詢問兩個結點之間的最小瓶頸路。u和v兩個結點之間最小瓶頸路指的是u和v的每條路徑中經過的最大邊權的最小值。強制在線，期望實現詢問時間復雜度為O(1)的算法。

題解：

給出結論：無向圖的最小瓶頸路與其最小生成樹上兩個結點之間最小瓶頸路值相等。
上面結論的證明我們可以參考Krusca求解最小生成樹的過程，對于當前可以加入的一條邊(u, v, w)，u和v之間的最小瓶頸路當前這條邊，因為在之前的過程中經過權重比w小的邊不能使u和v連通，根據這個過程我們便可以發現第一次讓u和v相連的邊的權重就是最小瓶頸路（這也是為什么Kruscal重構樹可以求最小瓶頸路的原理），而不難發現這個值也就是u和v路徑上的邊權最大值。
有了上面的說明，我們可以構造Kruscal重構樹，具體地：
使用Kruscal算法構造MST的時候，每選擇一條邊的時候，我們創建一個新的結點w，將u的根節點與w之間連接雙向邊，將v的根節點與w連接雙向邊，w的點權為當前選擇的邊的邊權。這樣構造出來的樹叫做Kruscal重構樹，不難發現，在該樹中兩個結點的LCA的點權為其最小瓶頸路（上面已經說明第一次合并的時候的邊權即為最小瓶頸路，而LCA的點權就是第一次合并時選擇邊的邊權）。我們不難發現深度越低的點的點權越大。
我們不難發現若初始有n個結點，那么Kruscal重構樹一共有2n-1個結點，因此現在的問題變成了：需要快速查詢兩個結點的LCA的點權。如果題目不要求在線，那么我們可以通過Tarjan在O(n+m)的復雜度求出所有詢問的LCA。
如果要求在線，我們可以借助Eular序和ST表實現，我們在DFS的過程中，在進入DFS的時候與訪問完某個兒子結點的時候對當前結點進行標號，同時記錄每個結點的第一次編號為in[u]。通過這樣操作后，對于詢問u和詢問v，那么對于編號in[u]~in[v]（或者in[v]~in[u]）中的所有編號均為LCA(u,v)所在子樹的結點的編號（這一點很容易思考，讀者可以自己思考）。
由于深度越大的點的點權越大，所以有了Eular序之后，問題就變成了詢問in[u]~in[v]（或者in[v]~in[u]）上的點權最小值，由于編號是連續的，我們可以使用ST表進行O(1)復雜度的查詢。

代碼：LibreOJ137