生成樹相關問題 -- 訓練指南

訓練指南裡提出了幾個經典的生成樹問題，我想做一點整理。
首先提出了最小生成樹有兩個性質：
1. 切割性質：任一個圖 G的子集 G'非空且不為 G本身，則其中一個端點在 G'裡，另一個端點在 G 的邊裡權值最小的必然會包含於 G的最小生成樹裡。
2. 迴路性質：任一個圖 G所含的環裡權值最大的邊必然不包含於 G的最小生成樹裡。
接下來是一些經典的生成樹問題：
1Q. 增量最小生成樹：初始時給 n個點的空圖，依次加入 m條帶權的邊，每加入一條邊就要輸出目前最小生成樹權值( 不聯通時輸出無解）。
1A. 首先很明顯最小生成樹只會越來越小。一旦最小生成樹存在，就刪去所有不在最小生成樹上的邊。根據樹的性質，加入一條新的邊後一定會產生洽一個環，這時候再根據迴路性質除去迴路上權
值最大的邊即可。如果用 BFS實現會有複雜度 O( m * n )。不過其實只保留最小生成樹的情況下直接用 Kruskal演算法暴力重構也不會太差 O( n * m * lg n )。
2Q. 最小瓶頸生成樹：求最大邊權最小的生成樹
2A. 如同 Kruskal演算法，由邊權小到大把每個邊都依序加入直到圖聯通。甚至不需要做並查集。
3Q. 最小瓶頸路徑：給一個點對 ( u, v )，求 u到 v的一條路徑，且路徑上邊權最大的邊最小。
3A. 令 ( u, v ) 的最小瓶頸路徑為 f( u, v )。當從原本的節點 u走訪到一個新的節點 v時，更新所有 u的前驅 x，f( x, v ) = max( f( x, u ), w( u, v ) )，複雜度 O( n * n )，靜態可以做 RMQ降到 O( n lg n + q lg n )。
4Q. 次小生成樹：所有生成樹權值和由大到小排序，排名第二的生成樹。比較特別的是，若最小生成樹不唯一，次小生成樹的權值會和最小生成樹相同。
4A. 一個暴力的做法是先求出最小生成樹，再一一枚舉要禁用的邊，每次重構一個最小生成樹，複雜度為O( m * lg * m + n * m * α( n, m ) )。一個更好的做法是考慮次小生成樹的性質「次小生成樹可以由最小生成樹刪除一條邊再加入補集裡的邊得到」，枚舉最小生成樹上的每條邊 u <-> v，由於樹的性質，加入這條邊後會產生迴路，所以根據最小生成樹的迴路性質要刪除的邊一定是原本的最小生成樹上 u到 v的路徑上權值最大的邊。具體的做法是在一開始求出最小生成樹後先預處理每對節點的最小瓶頸路徑 O( n * n )，就可以 O( 1 )計算替換後生成樹的權值總和。枚舉 O( m )，總複雜度 O( n * n + m )。
5Q. 最小有向生成樹：還沒理解，有空再來補

題目：
3:
基礎：UVA 1494
RMQ：UVA 11354