我這一題是用

1. DSU 結構

   • p[i]：並查集父指標，初始 p[i] = i。

   • has_special[i]：用來標記以「代表元 ii」為根的集合內，是否含有至少一個巨人城鎮。

2. 讀入與標記巨人

   • 先讀 N,M,KN,M,K。

   • 讀 KK 個住巨人的城鎮編號 aiai​，直接把 dsu.has_special[a_i] = true。

3. 桶排序

   • 因為 1≤c≤100001≤c≤10000，所以用 buckets 這種 vector of vector，只要額外開 1000110001 個桶，讀完每條邊就 buckets[c].push_back({u,v})。

   • 這步只要 O(M)O(M)，沒有額外的 log⁡MlogM 開銷。

4. 按權重掃描

   • 由 w=1w=1 掃到 w=10000w=10000，若 buckets[w] 裡有邊，就依序取出邊 (u,v)(u,v)：

     • 找出 ru = find(u)、rv = find(v)。

     • 如果同根或兩集合都已有巨人，就跳過。

     • 否則 unite(ru, rv)，並把 ww 加到 answer。

5. 時間複雜度

   • 桶排序「將 MM 條邊放桶」： O(M)O(M)。

   • 然後「遍歷 1000010000 個桶」：掃過每個桶的所有邊，共 MM 條，做 MM 次 find/unite，每次近似 O(α(N))≈O(1)O(α(N))≈O(1)。

   • 因此整體約 O(M+10000+Mα(N))≈O(M)O(M+10000+Mα(N))≈O(M)，遠快於 O(Mlog⁡M)O(MlogM) 或 O(Mlog⁡N)O(MlogN)。

這是我第二次優化的地方

• 扁平計數排序（Counting Sort）：一次性把所有邊根據權重 1…100001…10000 分到「連續陣列區段」，避免 std::vectorstd::vector 的額外開銷，也省去  O(Mlog⁡M)O(MlogM)\ 排序。

• DSU（並查集）用「按集合大小合併 + 路徑壓縮」，確保 α(N)α(N) 時間。

• 自訂快速輸入（FastIO），避免 cincin 或 scanfscanf 的額外負擔。