「問題 MST on Line」は以下のようにして解くことができます。

整数 \(\text{ans}\) と整数集合 \(S\) があります。初め \(\text{ans}=0,S=\{-\text{INF},\text{INF}\}\) です。

\(A_{P_{i}}\) が小さい \(i\) の順に以下の操作を順にします。

• \(l\) を \(S\) に含まれる \(i\) 以下の最大の整数、 \(r\) を \(S\) に含まれる \(i\) 以上の最小の整数とする。
• \(i-l\leq K\) なら \(\text{ans}+=A_{P_{i}}\)
• \(r-i\leq K\) なら \(\text{ans}+=A_{P_{i}}\)
• \(r-l\leq K\) なら \(\text{ans}-=A_{P_{i}}\)
• \(S\) に \(i\) を挿入する。

以下の操作を全ての \(i\) について行った後の \(\text{ans}\) が最小全域木の辺の重みの和となる。

\(A_{i}\) が \(\text{ans}\) に何回足されるかと何回引かれるかを全ての \(i\) について求めれば良いです。

\(A\) が昇順ソートされているとします。

\(A_{i}\) が足される回数は以下のようになります。

\[2(i-1)\cdot i!\cdot (N-1-i)!\sum_{k=1}^{K}\left( \begin{matrix} N-k\\ i-1\\ \end{matrix} \right)\]

\(A_{i}\) が引かれる回数は以下のようになります。

\[(i-2)\cdot i!\cdot (N-1-i)!\sum_{k=2}^{K}(k-1)\left( \begin{matrix} N-k\\ i-1\\ \end{matrix} \right)\]

よって、 時間計算量 \(O(N(K+\log{N}))\) で解くことができます。