グラフ理論の問題

重みの形. $i={\prod }_p{p}^{a_p}$, $j={\prod }_p{p}^{b_p}$ と素因数分解すると、$\mathrm{lcm}(i,j)={\prod }_p{p}^{\max (a_p,b_p)}$, $\gcd (i,j)={\prod }_p{p}^{\min (a_p,b_p)}$ なので
$$w(i,j)=\prod _p{p}^{|a_p-b_p|}.$$
よって $w(i,j)$ の素因数は、$i$ と $j$ で指数が異なる素数に限られる。特に、重みが $w$ 以下の辺で結ばれた 2 頂点は、$w$ より大きい素数の指数が等しい。

クラスカル法の考え方. 重みの小さい辺から順に、閉路を作らないものを採用していく（クラスカル法）と最小全域木が得られる。重み $w$ の辺の段階で採用される辺の本数は、「重み $w$ 未満の辺だけからなる部分グラフの連結成分数」から「重み $w$ 以下の辺だけからなる部分グラフの連結成分数」を引いたものに等しい。したがって、しきい値 $w$ を大きくしながら連結成分の変化を追えばよい。

重み 2. 重み 2 の辺は比が 2 の組 $\{m,2m\}$ である。各頂点 $n$ を $n=2^{k}m$（$m$ は奇数）と書くと、重み 2 の辺で $m,2m,4m,\dots$ が一列につながる。連結成分は奇数部分 $m\in \{1,3,5,\dots ,29\}$ ごとに 1 つずつで $15$ 個。採用辺数は $30-15=15$ 本、重みの和は $15\times 2=30$。

重み 3, 4. 重み 3 の辺は比が 3 の組で、奇数部分が $m$ と $3m$ の成分をつなぐ（$m,3m\le 30$ なら辺 $\{m,3m\}$ がある）。$1-3-9-27$, $5-15$, $7-21$ が併合され、$5$ 回の併合（重み和 $15$）で成分は $10$ 個：
$\{1,3,9,27\},\{5,15\},\{7,21\},\{11\},\{13\},\{17\},\{19\},\{23\},\{25\},\{29\}$（奇数部分で表示）。
重み 4 の辺は比が 4 の組で、奇数部分が同じなので併合は起こらない。

重み 5, 6. 重み 5 の辺は比が 5 の組で、$1-5$ により $\{1,3,9,27\}$ と $\{5,15\}$ が、$5-25$ により $\{25\}$ が併合される（$3-15$ は既に同じ成分、$7\cdot 5>30$）。$2$ 回の併合で重み和 $10$、成分は $8$ 個。重み 6 の辺は素数 2, 3 の指数だけが異なる組で、奇数部分が 3 のべき倍だけ異なるから既に同じ成分であり、併合は起こらない。

重み 7〜10. 重み 7 の辺 $\{1,7\}$ で $\{7,21\}$ が併合（重み和 $7$）、成分は $7$ 個：大きな成分（奇数部分 $1,3,5,7,9,15,21,25,27$）と $\{11\},\{13\},\{17\},\{19\},\{23\},\{29\}$。重み $8,9,10$ の辺は素数 $2,3,5$ の指数しか変えないので併合は起こらない。

残りの成分. 奇数部分が素数 $p\in \{11,13,17,19,23,29\}$ の成分（$\{11,22\}$ など）に属する頂点は $p$ の指数が 1、他の成分の頂点は $p$ の指数が 0 である（$30$ 以下で $p^2$ や、$p$ と別の奇素数の積は現れない）。よってこの成分と外を結ぶ辺の重みは $p$ の倍数で、$p$ 以上。一方、辺 $\{1,p\}$ の重みはちょうど $p$ であり、$p$ 未満のしきい値ではこの成分は孤立したままである。したがって各 $p$ について重み $p$ の辺が 1 本ずつ採用され、重み和は
$$11+13+17+19+23+29=112.$$

合計. 採用辺数は $15+5+2+1+6=29=30-1$ で全域木になっており、重みは
$$30+15+10+7+112=174.$$

重みは、$g=\gcd (i,j)$、$i=ga,j=gb$（$a,b$ は互いに素）とおくと $w(i,j)=ab$ となる。$i\ne j$ なので $w\ge 2$ である。クラスカル法で重みの小さい辺から順に調べる。

・重み 2：辺 $\{v,2v\}$。これで各頂点は「奇数部分」ごとの成分にまとまる。奇数部分は $1,3,\dots ,29$ の 15 個なので、成分は 15 個になる。この段階で 30 頂点から 15 本の辺を使い、重みの和は $15\times 2=30$。

・重み 3：$ab=3$ は $(1,3)$ のみで、辺は $\{v,3v\}$。奇数部分 $m$ と $3m$ を結ぶ。$1-3,3-9,9-27,5-15,7-21$ の 5 本がすべて別々の成分を結ぶ。和は 15。成分は 10 個になる。

・重み 4 は同じ奇数部分の内部の辺だけ、重み 6 は $m$ と $3m$ を結ぶだけなので、新たな連結は生じない。

・重み 5：$\{v,5v\}$。$1-5$ と $5-25$ が新しい連結を与え、$3-15$ は冗長。2 本で和は 10。

・重み 7：$1-7$（または $3-21$）が成分 $\{7,14,21,28\}$ を結ぶ。1 本で和は 7。

ここまでに、残る成分は 11, 13, 17, 19, 23, 29 を奇数部分にもつ 6 個。

・重み 8〜10 は新たな連結を生まない。

・これらの成分に属する頂点 $v$（$v=11,13,17,19,23,29$ およびその 2 倍）は、他の頂点 $u$ との辺の重みが、$g=1$ なら $vu\ge v$、$g>1$ でも $v$ 以上（$g=v$ のとき $u=kv$ で重みは $k$ だが $2v$ までしか取れず同じ成分内）となる。実際、各成分から他成分へ出る辺の最小重みは、順に 11, 13, 17, 19, 23, 29 である（頂点 1 との辺）。

・よって、残り 6 本の辺の重みの和は $11+13+17+19+23+29=112$。

辺の総数は $15+5+2+1+6=29=30-1$ で適合する。

合計は $30+15+10+7+112=174$。