\(6\) 辺のうちサイクルに含まれない \(2\) 辺を考えます。\(2\) 辺の組としてあり得るものは以下の \(3\) 通りです。

• 辺 \((1,2)\) と辺 \((3,4)\)
• 辺 \((1,3)\) と辺 \((2,4)\)
• 辺 \((1,4)\) と辺 \((2,3)\)

この \(3\) つのグループの辺の重みの和をそれぞれ \(A, B, C\) とします。 そのようなグラフの個数は \((A-1)(B-1)(C-1)\) であり、各グラフ \(G\) について \(f(G) = K - \max(A,B,C)\) となるため、 \(A,B,C\) を固定したときの \(f(G)\) の和を \(O(1)\) で求められます。

\(A+B+C=K\) より、\(A,B,C\) の全探索を \(O(K^2)\) で行えるため、この問題を \(O(K^2)\) で解くことができます。