この問題を \(O((N + Q)^2)\) 時間で解く方法を紹介します．

現在の頂点数を \(n\) として，連結成分の管理に \(n\) 頂点の UnionFind を用います．

連結成分間の距離の情報を，UnionFind のリーダーに集約して持たせると効率的になりそうです．そこで，\(n \times n\) の配列 \(\text{dist}\) を，

• \(i \neq j\) かつ \(i\) も \(j\) も UnionFind のリーダーなら，\(\text{dist}[i][j] = (\) 連結成分 \(i\) と連結成分 \(j\) の間の距離 \()\)
• そうでないなら，\(\text{dist}[i][j] = \infty\)

となるように管理します．

連結成分のマージは \(O(N + Q)\) 回発生します．

• 連結成分をマージするときの \(\text{dist}\) の更新
• 頂点を追加するときの \(\text{dist}\) の更新

は \(O(n)\) 時間でできるので，あとは，\(O(n)\) 時間で

• 最小の距離 \(k\) と，それを達成する連結成分の組を \(1\) つ発見

ができれば良いです．

そこで，長さ \(n\) の配列 \(\text{mn}\) を，

• \(i\) が UnionFind のリーダーなら，\(\text{mn}[i] = \min(\text{dist}[i])\)
• そうでないなら，\(\text{mn}[i] = \infty\)

となるように管理します．これを用いれば，

• 最小の距離 \(k\) と，それを達成する連結成分の組を \(1\) つ発見
• 頂点を追加するときの \(\text{mn}\) の更新

は \(O(n)\) 時間で可能です．一見，

• 連結成分をマージするときの \(\text{mn}\) の更新

が \(O(n)\) 時間でできないように見えますが，リーダー \(a\) とリーダー \(b\) をマージするときに変化する場所は \(\text{mn}[a], \text{mn}[b]\) の \(2\) 箇所しかないため，これも \(O(n)\) 時間で可能です．

実装例 (C++, 89 ms)

さらに，以下のように高速化を行うことができます．

(1) \(\text{dist}\) の定義を (連結成分) 対 (頂点) とすることで，更新箇所が減らせます．

• \(i\) が UnionFind のリーダーで，頂点 \(j\) が連結成分 \(i\) に含まれないなら，\(\text{dist}[i][j] = (\) 連結成分 \(i\) と頂点 \(j\) の間の距離 \()\)
• \(i\) が UnionFind のリーダーで，頂点 \(j\) が連結成分 \(i\) に含まれるなら，\(\text{dist}[i][j] = \infty\)

(2) 頂点 \(i, j\ (i > j)\) 間の距離が \(\text{dist}[\text{leader}(i)][j]\) と \(\text{dist}[\text{leader}(j)][i]\) の \(2\) 箇所で管理されていますが，これを \(\text{dist}[\text{leader}(i)][j]\) のみにします．さらに，UnionFind のリーダーを「連結成分の中で index が最大の頂点」とすることで，\(\text{dist}\) の下三角部分しか必要なくなります．

(1) と (2) により，ボトルネック部分がすべてシーケンシャルアクセスになります．

実装例 (C++, 21 ms)

(3) ボトルネック部分を AVX512 を用いてベクトル化することで，11 ms を達成することができます．

実装例 (C++, 11 ms)