HDU 5333 Undirected Graph：LCT (Link-Cut Tree) + BIT 維護動態連通分量

題目大意

給定 n 點 m 邊無向圖（含自環、重邊），q 次詢問 [L, R]。每次詢問：刪除所有至少一個端點不在 [L, R] 的邊，求剩餘圖的連通分量數。詢問獨立（每次從原圖刪除）。
n, q ≤ 10⁵，m ≤ 2×10⁵，至少 97% 測資 n, m, q ≤ 1000。

核心轉化：連通分量 = 點數 - 生成森林邊數

對誘導子圖 G[L, R]，其連通分量數 = (R-L+1) - (生成森林邊數)。
生成森林邊數 = 不形成環的邊數。即：按任意順序加入邊，若該邊連接兩個不同連通分量（不成環），計數 +1。

離線掃描 + LCT 維護動態森林

• 將邊 (u, v) 標準化為 u < v，按 v 遞增排序（即按右端點掃描）。
• 掃描 R = 1..n，維護當前 [1, R] 內的生成森林（用 LCT 表示）。
• 加入邊 (u, v)（v == R）：
  • 若 u, v 不連通（findRoot(u) != findRoot(v)），直接 link(u, v)，該邊入森林，BIT.add(v, 1) 記錄「以 v 為右端點的森林邊」。
  • 若已連通，找路徑上最小左端點的邊（用 LCT 節點維護 val=左端點、min_id）。若該最小左端點 >= u，則新邊無優勢，丟棄；否則 cut 掉那條舊邊（BIT.add(old_id, -1)），link 新邊（BIT.add(v, 1)）。此即「用右端點固定、左端點更小的邊替換舊邊」，保證森林邊的左端點盡可能小，從而最大化未來查詢 [L, R] 時的合法邊數。
• 處理詢問 [L, R]（按 R 分組）：答案 = (R-L+1) - BIT.query(L, R)。BIT 統計當前森林中右端點在 [L, R] 的邊數，即生成森林邊數。

LCT 關鍵字段

• val：該節點代表的邊的左端點（頂點節點 val=0）。
• mi, min_id：子樹內最小 val 及對應節點 id。
• makeRoot, access, link, cut, findRoot 標準操作。

複雜度

• LCT 操作均攤 O(log n)，總 O((m+q) log n)。
• 常數較大，需快速 IO、靜態節點池、手動棧擴大（#pragma comment(linker,...)）。

總結

本題是「區間誘導子圖連通分量」的離線經典解法：按右端點掃描 + LCT 維護最優生成森林（左端點最小化）+ BIT 統計區間森林邊數。LCT 內部維護「路徑最小左端點」以支持「替換更優邊」是核心技巧。代碼量大、常數大，屬於高難度數據結構題。