問題

https://atcoder.jp/contests/abc352/tasks/abc352_e

解説の前にクリークについて.

• グラフ理論において、無向グラフ $G = (V,E)$ のクリーク(英: clique) とは、頂点の部分集合 $C \subseteq V$ のうち、$C$ に属するあらゆる2つの頂点を繋ぐ辺が存在するものをいう。

つまり頂点の部分集合 $C$ の完全グラフのこと.

問題を整理すると

クリークがたくさん与えられるからその中から適当な辺を拾って最小全域木の重みを答えろ という問題に言い換えられる.

計算量を無視して答えをナイーブに求めるやり方を考える.

クラスカル法(またはプリム法など)で重みが小さい辺から確定していく解放がまず思いつく.

制約を見ると頂点の部分集合を全パターン試してUnionFindで繋げて…みたいな悠長なことしてると $\Omicron(10^{11})$ ぐらいの計算量になる.

もう少し制約を眺めると集合として与えられる頂点の総数は $4 \times 10^5$ なのでこれをうまく使えば通りそう.

クリーク同士が連結していて全部の頂点を含んでいたら最小全域木を作れるはず.

クリークを $C$ としたとき,

最小全域木が作れるクリークを与えられたとして,任意の頂点 $c \in C$ から $c$ 以外の頂点に辺を繋ぐ行為を全てのクリークに対して行えばそれはクリークの順序,選ぶ頂点,繋ぐ順番に関わらず全域木になるはずである.