木の場合に dfs で最適解を実現する公式解説の解法はある種の典型的な発想ではありますが、直接全域木について考えることを思いつかなくても、例えば以下のように考えることができます。

ある単純閉路があり、その辺が順に辺 \(p_1, p_2, \cdots ,p_k\) だったとします。

例えば辺 \(p_1\) を一度選ぶような操作列によるランプの光り方は、辺 \(p_1\) を選ばず辺 \(p_2, p_3, \cdots ,p_k\) を全て追加で \(1\) 回選ぶ操作列でも実現できます。(証明は簡単です) そのため、辺 \(p_1\) を取り除いても実現できるランプの光り方の集合は変わりません。

この議論を続けることで、グラフに単純閉路がなくなるまで、つまり森になるまで辺を減らすことができます。このことを考えると、ある全域森をとってそのグラフについて考察すれば問題ないことがわかります。以降は公式解説と同様です。