公式解説では\(1+3+⋯+(2k+1)=k^2\) を利用していい感じに構築していますが、２つの選択間のコストがある性質を満たすならば機械的にグラフを構築することができます。

参考

似た問題