公式解説と同じ計算量で，半分全列挙 + DP でも解くことができます．

交差点集合を \(S, T\) に二等分します．まず，\(S\) 側の交差点への設置の仕方 \(2^{N/2}\) 通りすべてに対して，

• 監視済みの道の数の偶奇 \(\mathrm{par}[*] \in \{0, 1\}\)
• \(T\) 側の各交差点 \(t\) 周りで未監視の道の数の偶奇 \(\mathrm{par}[t] \in \{0, 1\}\)

がどういう状態（全部で \(2^{N/2 + 1}\) 通り）となっているかを確認し，各状態の数を計算します． これは，監視済みの道の数と各頂点の次数（未監視の道のみ）の偶奇を管理しながら深さ優先探索的に行うことで，全体で \(\mathrm{O}(N 2^{N/2})\) 時間で計算できます．

上で計算した各状態の数を初期値として，\(T\) 側の各交差点に対して追加で設置するかどうか決めたときに，各状態の数がどう変化するかを DP で計算します． 具体的には，\(T\) 側の交差点を任意の順で選び，以下の処理を行います． 交差点 \(t \in T\) を選んだとき，以下のように状態が変化するので，その状態の数に現在の状態の数を加算します．

• \(t\) に設置しないなら同じ状態．
• \(t\) に設置するなら，\(\mathrm{par}[*] \leftarrow \mathrm{par}[*] \oplus \mathrm{par}[t]\)，

  \[\mathrm{par}[t'] \leftarrow \begin{cases} \mathrm{par}[t'] \oplus 1 & (\,t'\, は\, t\, に隣接している)\\ \mathrm{par}[t'] & (\,t'\, は\, t\, に隣接していない) \end{cases}\]

  と更新された状態．

ただし，\(t\) 自身の状態はそれ以降必要無いので，\(\mathrm{par}[t]\) の値は忘れて纏めてしまって構いません． したがって，交差点を \(1\) つ処理するごとに状態として考えるべきものを \(2^{N/2 + 1}, 2^{N/2}, \dots, 2^1\) 個と半分ずつにでき，その総和は \(2^{N/2 + 2} - 2 = \Theta(2^{N/2})\) です． 各遷移（どの状態の数に現在の状態の数を加算すべきかの計算）は \(\mathrm{O}(N)\) 時間でできるので，DP の計算時間も \(\mathrm{O}(N 2^{N/2})\) となります． 最終的に得られる \(\mathrm{par}[*] = 0\) の状態の数が答えです．

以上より，全体として \(\mathrm{O}(N 2^{N/2})\) 時間でこの問題が解けました．

実装例