比較正式的作法

> (先備知識)持久化並查集 https://blog.csdn.net/AaronGZK/article/details/51511601

開持久化線段樹去維護啟發式並查集，再對時間軸二分搜

對時間軸二分搜，如果當前時刻已經 (u,v) 已經連通了，則將時間右界移動至中心，否則將時間左界移動到中心。

1. 合併時，O(lgN lgN)

2. 查詢時，O(lgM lgN lgN)

這時間複雜度聽起來就很毒瘤><

-

離線大法才是王道

> (先備知識)預處理倍增法 LCA https://blog.csdn.net/Hanks_o/article/details/77799320

預設圖 G 空白，如果 (u,v) 連通，將查詢 (u,v) 存入代辦事項中；如果 (u,v) 不連通，在圖 G 中加入一條權重為 time 的邊。

在圖 G 上建構 dfs tree，預處理倍增法 LCA。

對於查詢兩點 (u,v) 在什麼時候開始連通，等價於在圖 G 上，從 u 移動到 LCA(u,v) ，再從 LCA(u,v) 移動到 v 上，經過所有邊權重的最大值。

路徑 P = [u -> u 的父節點 -> u 的爺節點 -> ... -> LCA(u,v) -> ... -> v 的爺節點 -> v 的父節點 -> v] 

查詢兩點 (u,v) 在什麼時候開始連通，等價路徑 P 上權重的最大值。

1. 判斷 (u,v) 連通，使用路徑壓縮式並查集 O(a(N))

2. 預處理倍增法 LCA，O(N log N)

3. 回答所有查詢，其中有 Q 個查詢，O(Q log N)

這時間複雜度聽起來就很正常><