https://emtubasa.hateblo.jp/entry/2021/10/29/192109

問題
 提出コード
解説見たらやっていることが少し違ったのでメモしておきます。

まず、同じ頂点のボタンを2回押すと元に戻るので、それぞれのボタンについては"押す"か、"押さない"かの2通りだけ考えれば良いです。
そして、全ての頂点を1度押すことを考えます。すると、全ての辺について、色が変わる回数は2回になります(辺に繋がっている頂点が2個なので)。
つまり、ある頂点集合 $S$ について考えると、その補集合を押した時と結果は同じになります。このことから、頂点 $1$ を押す、として最適解を探した時も頂点 $1$ を押さない、とした時も結果は同じです。
よって、頂点 $1$ は押さない、と確定させることができます。
今回作りたいのは全域木です。頂点 $1$ と頂点 $y$ を繋ぐ、としましょう。
頂点 $1$ については押さないことが確定しているので、 $(1,y)$ の辺が赤になるよう、頂点 $y$ で調整をする必要があります。この時点で、 $y$ の押す/押さないが確定します。
$1,y$ 以外の頂点 $x$ について見てみると、

$x$ を押す/押さないで、頂点 $1/y$ のどちらと繋がっているかが切り替わる
$x$ を押す/押さないで、頂点 $1,y$ の両方と繋がっている/繋がっていないが切り替わる

の2パターンに分かれます。後者については、繋がっているを選択すると、 $1-x-y-1$ の閉路ができるので、繋がっていないを選択するしかありません。よって、このパターンについては操作が一意に決まります。
前者のパターンの頂点集合を $A = \{a,b,c,\ldots\}$ としましょう。
$a$ について、押す/押さないを決めてみます。すると、 $b,c,\ldots$ のそれぞれについて、 $a$ と繋がっている辺が赤くなるパターンと、黒くなるパターンが、押す/押さないで決まります。赤いパターンを選択してしまうと、頂点 $1,y$ を含んだ閉路が必ずできてしまうので、黒くなるパターンを選択するしかありません。
ここまでで、全ての頂点の押す/押さないが確定しました( $A$ が空の場合もありますが、そのときは空とわかった時点で、全ての頂点の押す/押さないが確定しています)。
あとは、押した結果グラフが全域木になっているか確認してペナルティを計算すれば良いです。
$y$ を決めるので $O(N)$ 、 $A$ について押す/押さないを確認するので $O(N)$ 、押す操作を実際に行うので $O(N)$ で、結局 $O(N^{3})$ です。
チェックするパートについても、全ての辺を愚直に走査すれば良いです。たかだか $O(N)$ 回しかチェックしないので、こちらも $O(N^{3})$ になります。

感想

昔見た時は全く歯が立ちませんでしたが、今解いたら順調に考察が進んだので面白かったです。
昔一度解説を見て感動した記憶がありますが、全然違う考察ルートを辿ったので、記憶に残っていないことがバレました。